什么是函数式语言中的“模式匹配”?

我正在阅读关于函数式编程的文章,我注意到许多文章都提到模式匹配是函数式语言的核心特性之一。

有人能为Java / C ++ / JavaScript开发人员解释这是什么意思吗?

9个解决方案
126 votes

了解模式匹配需要解释三个部分:

  1. 代数数据类型。
  2. 什么模式匹配
  3. 为什么它真棒。

代数数据类型简而言之

类似ML的函数式语言允许您定义称为"不相交联合的简单数据类型" 或"代数数据类型"。 这些数据结构是简单的容器,可以递归地定义。 例如:

type 'a list =
    | Nil
    | Cons of 'a * 'a list

定义类似堆栈的数据结构。 可以认为它等同于这个C#:

public abstract class List<T>
{
    public class Nil : List<T> { }
    public class Cons : List<T>
    {
        public readonly T Item1;
        public readonly List<T> Item2;
        public Cons(T item1, List<T> item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }
}

因此,let x = Node(Nil, 1, Nil)rotateLeft x标识符定义了一个简单类,其中x定义了构造函数和一些数据类型。 构造函数的参数是未命名的,它们由位置和数据类型标识。

您可以创建let x = Node(Nil, 1, Nil)类的实例:

let x = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))

这与:

Stack<int> x = new Cons(1, new Cons(2, new Cons(3, new Cons(4, new Nil()))));

模式匹配简而言之

模式匹配是一种类型测试。 所以,让我们说我们创建了一个像上面那样的堆栈对象,我们可以实现方法来查看和弹出堆栈,如下所示:

let peek s =
    match s with
    | Cons(hd, tl) -> hd
    | Nil -> failwith "Empty stack"

let pop s =
    match s with
    | Cons(hd, tl) -> tl
    | Nil -> failwith "Empty stack"

上述方法与以下C#等效(尽管未实现):

public static T Peek<T>(Stack<T> s)
{
    if (s is Stack<T>.Cons)
    {
        T hd = ((Stack<T>.Cons)s).Item1;
        Stack<T> tl = ((Stack<T>.Cons)s).Item2;
        return hd;
    }
    else if (s is Stack<T>.Nil)
        throw new Exception("Empty stack");
    else
        throw new MatchFailureException();
}

public static Stack<T> Pop<T>(Stack<T> s)
{
    if (s is Stack<T>.Cons)
    {
        T hd = ((Stack<T>.Cons)s).Item1;
        Stack<T> tl = ((Stack<T>.Cons)s).Item2;
        return tl;
    }
    else if (s is Stack<T>.Nil)
        throw new Exception("Empty stack");
    else
        throw new MatchFailureException();
}

(几乎总是,ML语言在没有运行时类型测试或强制转换的情况下实现模式匹配,因此C#代码有点欺骗性。让我们的刷子实现细节放在一边请一些挥手请:))

简而言之,数据结构分解

好的,让我们回到peek方法:

let peek s =
    match s with
    | Cons(hd, tl) -> hd
    | Nil -> failwith "Empty stack"

诀窍是理解let x = Node(Nil, 1, Nil)rotateLeft x标识符是变量(错误......因为它们是不可变的,它们不是真正的&#34;变量&#34;,但是&#34;值&#34; ;))。 如果x的类型为Nil,那么我们将从构造函数中提取其值并将它们绑定到名为Nodex -> x的变量。

模式匹配很有用,因为它允许我们通过其形状而不是其内容来分解数据结构。 因此,假设我们如下定义二叉树:

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

我们可以定义一些树旋转如下:

let rotateLeft = function
    | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
    | x -> x

let rotateRight = function
    | Node(Node(a, p, b), q, c) -> Node(a, p, Node(b, q, c))
    | x -> x

let x = Node(Nil, 1, Nil)构造函数是rotateLeft x的语法糖。)

因此,除了将数据结构绑定到变量之外,我们还可以深入研究它。 让我们说我们有一个节点let x = Node(Nil, 1, Nil).如果我们调用rotateLeft x,我们针对第一个模式测试x,该模式无法匹配,因为右边的孩子的类型为Nil而不是Node.它将移动到下一个模式 ,x -> x,它将匹配任何输入并返回未修改。

为了比较,我们在C#中编写上述方法:

public abstract class Tree<T>
{
    public abstract U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc);

    public class Nil : Tree<T>
    {
        public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc)
        {
            return nilFunc();
        }
    }

    public class Node : Tree<T>
    {
        readonly Tree<T> Left;
        readonly T Value;
        readonly Tree<T> Right;

        public Node(Tree<T> left, T value, Tree<T> right)
        {
            this.Left = left;
            this.Value = value;
            this.Right = right;
        }

        public override U Match<U>(Func<U> nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc)
        {
            return nodeFunc(Left, Value, Right);
        }
    }

    public static Tree<T> RotateLeft(Tree<T> t)
    {
        return t.Match(
            () => t,
            (l, x, r) => r.Match(
                () => t,
                (rl, rx, rr) => new Node(new Node(l, x, rl), rx, rr))));
    }

    public static Tree<T> RotateRight(Tree<T> t)
    {
        return t.Match(
            () => t,
            (l, x, r) => l.Match(
                () => t,
                (ll, lx, lr) => new Node(ll, lx, new Node(lr, x, r))));
    }
}

对于认真。

模式匹配非常棒

你可以使用访问者模式在C#中实现类似于模式匹配的东西,但它不是那么灵活,因为你不能有效地分解复杂的数据结构。 此外,如果您使用模式匹配,编译器将告诉您是否遗漏了案例。 这有多棒?

考虑如何在没有模式匹配的情况下在C#或语言中实现类似功能。 想想你如何在没有运行时的测试和强制转换的情况下做到这一点。 它当然不难,只是繁琐和笨重。 而且你没有让编译器检查以确保你已经涵盖了所有案例。

因此,模式匹配可以帮助您以非常方便,紧凑的语法分解和导航数据结构,它使编译器能够检查代码的逻辑,至少是一点点。 这真的是一个杀手级的功能。

Juliet answered 2019-07-02T20:31:16Z
30 votes

简短回答:模式匹配的产生是因为函数式语言将等号作为等价的断言而不是赋值。

答案很长:模式匹配是一种基于其给出的值的“形状”的调度形式。 在函数式语言中,您定义的数据类型通常是所谓的区分联合或代数数据类型。 例如,什么是(链接)列表? 某个类型a = b的链接列表=是列表a或某些类型的元素b =ed到let Cons a (Cons b Nil) = frob xCons a (Cons b Nil)s的列表)。 在Haskell(我最熟悉的函数式语言)中,我们写了这个

data List a = Nil
            | Cons a (List a)

所有受歧视的联合都是这样定义的:单一类型有不同的方式来创建它; 这里的创建者,如=a = b,被称为构造函数。 这意味着可以使用两个不同的构造函数创建类型a的值 - 它可以具有两个不同的形状。 因此,假设我们要编写一个b函数来获取列表的第一个元素。 在Haskell中,我们将其写为

-- `head` is a function from a `List a` to an `a`.
head :: List a -> a
-- An empty list has no first item, so we raise an error.
head Nil        = error "empty list"
-- If we are given a `Cons`, we only want the first part; that's the list's head.
head (Cons h _) = h

由于=值可以是两种不同的类型,我们需要分别处理每一种; 这是模式匹配。 在a = b中,如果a与模式b匹配,那么我们运行第一个案例; 如果它匹配模式=,我们运行第二个。

简短的回答,解释说:我认为考虑这种行为的最好方法之一是改变你对等号的看法。 在大括号中,=表示赋值:a = b表示“make a into b”。然而,在许多函数式语言中,=表示相等的断言:let Cons a (Cons b Nil) = frob x断言左边的东西,Cons a (Cons b Nil) ,相当于右边的东西,frob x; 此外,左侧使用的所有变量都可见。 这也是函数参数发生的事情:我们断言第一个参数看起来像Nil,如果它没有,我们继续检查。

Antal Spector-Zabusky answered 2019-07-02T20:32:14Z
18 votes

这意味着不是写作

double f(int x, int y) {
  if (y == 0) {
    if (x == 0)
      return NaN;
    else if (x > 0)
      return Infinity;
    else
      return -Infinity;
  } else
     return (double)x / y;
}

你可以写

f(0, 0) = NaN;
f(x, 0) | x > 0 = Infinity;
        | else  = -Infinity;
f(x, y) = (double)x / y;

嘿,C ++也支持模式匹配。

static const int PositiveInfinity = -1;
static const int NegativeInfinity = -2;
static const int NaN = -3;

template <int x, int y> struct Divide {
  enum { value = x / y };
};
template <bool x_gt_0> struct aux { enum { value = PositiveInfinity }; };
template <> struct aux<false> { enum { value = NegativeInfinity }; };
template <int x> struct Divide<x, 0> {
  enum { value = aux<(x>0)>::value };
};
template <> struct Divide<0, 0> {
  enum { value = NaN };
};

#include <cstdio>

int main () {
    printf("%d %d %d %d\n", Divide<7,2>::value, Divide<1,0>::value, Divide<0,0>::value, Divide<-1,0>::value);
    return 0;
};
kennytm answered 2019-07-02T20:32:48Z
7 votes

模式匹配有点像类固醇上的重载方法。 最简单的情况与您在java中看到的大致相同,参数是带有名称的类型列表。 调用的正确方法基于传入的参数,并且它还可以作为参数名称的参数的赋值。

模式只是更进一步,可以进一步破坏传递的参数。 它还可以使用防护来根据参数的值实际匹配。 为了演示,我假装像JavaScript一样有模式匹配。

function foo(a,b,c){} //no pattern matching, just a list of arguments

function foo2([a],{prop1:d,prop2:e}, 35){} //invented pattern matching in JavaScript

在foo2中,它期望a是一个数组,它将第二个参数分开,期望一个带有两个props(prop1,prop2)的对象,并将这些属性的值赋给变量d和e,然后期望第三个参数为35。

与JavaScript不同,具有模式匹配的语言通常允许具有相同名称但具有不同模式的多个函数。 这样就像方法重载一样。 我将在erlang中举个例子:

fibo(0) -> 0 ;
fibo(1) -> 1 ;
fibo(N) when N > 0 -> fibo(N-1) + fibo(N-2) .

模糊你的眼睛,你可以想象这在JavaScript中。 这样的事情可能是:

function fibo(0){return 0;}
function fibo(1){return 1;}
function fibo(N) when N > 0 {return fibo(N-1) + fibo(N-2);}

重点是当你调用fibo时,它使用的实现基于参数,但是Java仅限于类型作为重载的唯一方法,模式匹配可以做更多。

除了这里所示的函数重载之外,相同的原理可以应用于其他地方,例如case语句或解构分配。 JavaScript甚至在1.7中都有这个。

Russell Leggett answered 2019-07-02T20:33:58Z
6 votes

模式匹配允许您将值(或对象)与某些模式匹配,以选择代码的分支。 从C ++的角度来看,它可能听起来有点类似于Circle(0, 0, radius)语句。 在函数式语言中,模式匹配可用于匹配标准原始值,例如整数。 但是,它对组合类型更有用。

首先,让我们演示原始值的模式匹配(使用扩展的伪C ++ Circle(0, 0, radius)):

switch(num) {
  case 1: 
    // runs this when num == 1
  case n when n > 10: 
    // runs this when num > 10
  case _: 
    // runs this for all other cases (underscore means 'match all')
}

第二种用途涉及功能数据类型,例如元组(允许您将多个对象存储在单个值中)和区分联合,允许您创建可包含多个选项之一的类型。 这听起来有点像Circle(0, 0, radius),除了每个标签还可以携带一些值。 在伪C ++语法中:

enum Shape { 
  Rectangle of { int left, int top, int width, int height }
  Circle of { int x, int y, int radius }
}

Circle(0, 0, radius)类型的值现在可以包含带有所有坐标的radius或带有中心和半径的Circle。 模式匹配允许您编写用于处理Shape类型的函数:

switch(shape) { 
  case Rectangle(l, t, w, h): 
    // declares variables l, t, w, h and assigns properties
    // of the rectangle value to the new variables
  case Circle(x, y, r):
    // this branch is run for circles (properties are assigned to variables)
}

最后,您还可以使用结合了这两个功能的嵌套模式。 例如,您可以使用Circle(0, 0, radius)来匹配在点[0,0]中具有中心且具有任何半径的所有形状(半径的值将分配给新变量radius)。

从C ++的角度来看,这可能听起来有些陌生,但我希望我的伪C ++能够清楚地解释这个问题。 函数式编程基于完全不同的概念,因此在函数式语言中更有意义!

Tomas Petricek answered 2019-07-02T20:35:02Z
4 votes

模式匹配是指您的语言的解释器将根据您提供的参数的结构和内容选择特定函数的位置。

它不仅是一种功能语言功能,而且可用于许多不同的语言。

我第一次遇到这个想法是因为我学习了prolog,它对语言来说非常重要。

例如

last([LastItem],LastItem)。

last([Head | Tail],LastItem): -        last(Tail,LastItem)。

上面的代码将给出列表的最后一项。 输入arg是第一个,结果是第二个。

如果列表中只有一个项目,则解释器将选择第一个版本,第二个参数将设置为等于第一个,即将为结果分配一个值。

如果列表同时具有头部和尾部,则解释器将选择第二个版本并递归,直到列表中只剩下一个项目。

charlieb answered 2019-07-02T20:36:19Z
3 votes

你应该从维基百科页面开始,给出一个非常好的解释。 然后,阅读Haskell wikibook的相关章节。

这是上面wikibook的一个很好的定义:

所以模式匹配是一种方式   为事物分配名称(或绑定   那些东西的名字),和   可能打破表达   同时进入子表达式   (正如我们对中的列表所做的那样)   地图的定义)。

Eli Bendersky answered 2019-07-02T20:37:00Z
3 votes

对于很多人来说,如果提供一些简单的例子,那么选择一个新概念会更容易,所以我们在这里:

让我们假设您有一个包含三个整数的列表,并希望添加第一个和第三个元素。 没有模式匹配,你可以这样做(Haskell中的例子):

Prelude> let is = [1,2,3]
Prelude> head is + is !! 2
4

现在,虽然这是一个玩具示例,但想象一下我们想将第一个和第三个整数绑定到变量并对它们求和:

addFirstAndThird is =
    let first = head is
        third = is !! 3
    in first + third

从数据结构中提取值是模式匹配的作用。 你基本上&#34;镜像&#34; 某事物的结构,给出了为感兴趣的地方绑定的变量:

addFirstAndThird [first,_,third] = first + third

当你用[1,2,3]作为参数调用这个函数时,[1,2,3]将与[first,_,third]统一,首先绑定到1,第三个绑定到3并丢弃2(_是 你不关心的事情的占位符。

现在,如果您只想将列表与2作为第二个元素进行匹配,则可以这样做:

addFirstAndThird [first,2,third] = first + third

这仅适用于将2作为其第二个元素的列表,否则抛出异常,因为没有为非匹配列表提供addFirstAndThird的定义。

到目前为止,我们仅将模式匹配用于解构绑定。 在上面,您可以给出相同函数的多个定义,其中使用了第一个匹配定义,因此,模式匹配有点像&#34;关于立体声的开关语句&#34;:

addFirstAndThird [first,2,third] = first + third
addFirstAndThird _ = 0

addFirstAndThird将愉快地添加列表的第一个和第三个元素,其中2作为第二个元素,否则&#34;通过&#34; 并且&#34;返回&#34; 这个&#34;开关式&#34; 功能不仅可以用在函数定义中,例如:

Prelude> case [1,3,3] of [a,2,c] -> a+c; _ -> 0
0
Prelude> case [1,2,3] of [a,2,c] -> a+c; _ -> 0
4

此外,它不仅限于列表,也可以与其他类型一起使用,例如匹配Maybe类型的Just和Nothing值构造函数,以便&#34; unwrap&#34; 价值:

Prelude> case (Just 1) of (Just x) -> succ x; Nothing -> 0
2
Prelude> case Nothing of (Just x) -> succ x; Nothing -> 0
0

当然,这些仅仅是玩具的例子,我甚至没有尝试给出正式或详尽的解释,但它们应该足以掌握基本概念。

danlei answered 2019-07-02T20:38:39Z
2 votes

这是一个非常简短的示例,显示了模式匹配的有用性:

我们假设您要对列表中的元素进行排序:

["Venice","Paris","New York","Amsterdam"] 

(我已整理好#34;纽约&#34;)

["Venice","New York","Paris","Amsterdam"] 

用更强制性的语言你会写:

function up(city, cities){  
    for(var i = 0; i < cities.length; i++){
        if(cities[i] === city && i > 0){
            var prev = cities[i-1];
            cities[i-1] = city;
            cities[i] = prev;
        }
    }
    return cities;
}

在函数式语言中,您可以改为:

let up list value =  
    match list with
        | [] -> []
        | previous::current::tail when current = value ->  current::previous::tail
        | current::tail -> current::(up tail value)

正如您所看到的模式匹配解决方案具有更少的噪音,您可以清楚地看到不同的情况,以及它们如何轻松地移动和解构我们的列表。

我在这里写了一篇关于它的更详细的博客文章。

foobarcode answered 2019-07-02T20:39:47Z
translate from https://stackoverflow.com:/questions/2502354/what-is-pattern-matching-in-functional-languages