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

我正在阅读函数式编程,而且我注意到, 模式匹配在许多文章中被提及为函数式语言的核心特性之一。

有人可以解释一个Java / C ++ / JavaScript开发者是什么意思?

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

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

简而言之,代数数据types

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

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; } } } 

所以, ConsNil标识符定义了一个简单的类,其中of x * y * z * ...定义了一个构造函数和一些数据types。 构造函数的参数是未命名的,它们由位置和数据types来标识。

你创builda list类的实例,如下所示:

 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())))); 

模式匹配简而言之

模式匹配是一种typestesting。 假设我们创build了一个像上面那样的堆栈对象,我们可以实现方法来查看和popup堆栈,如下所示:

 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语言都是在没有运行时typestesting的情况下实现模式匹配的,所以C#代码有点欺骗性,让我们把实现的细节抛在一边,请稍微挥手:))

数据结构分解简而言之

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

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

技巧是理解hdtl标识符是variables(errm …因为它们是不可变的,它们不是真正的“variables”,而是“值”);))。 如果s的types为Cons ,那么我们Cons构造函数中取出它的值,并将它们绑定到名为hdtlvariables。

模式匹配是有用的,因为它使我们能够根据其形状而不是其内容来分解数据结构。 所以想象一下,如果我们定义一个二叉树如下:

 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 rotateRight = function构造函数是let rotateRight s = match s with ...语法sugar)

所以除了将数据结构绑定到variables之外,我们还可以深入研究它。 假设我们有一个节点let x = Node(Nil, 1, Nil) 。 如果我们调用rotateLeft x ,我们会针对第一个模式来testingx ,由于右边的子代types为Nil而不是Node ,所以无法匹配。 它将移动到下一个模式, x -> x ,它将匹配任何input,并且不加修改地返回它。

为了比较,我们将上面的方法写在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#或语言中实现类似的function,而没有模式匹配。 考虑一下如何在没有testingtesting的情况下进行testing,并在运行时进行强制转换。 它当然不难 ,只是笨重和笨重。 你没有编译器检查,以确保你已经覆盖了每一个案件。

因此,模式匹配可以帮助您以非常方便,简洁的语法分解和导航数据结构,从而使编译器至less可以检查代码的逻辑 。 这确实一个杀手级的function。

简而言之:模式匹配的出现是因为function性语言把等号当作等价断言而不是赋值。

长答案:模式匹配是一种基于给定值“形状”的调度forms。 在函数式语言中,您定义的数据types通常是被称为区分的联合或代数数据types。 例如,什么是(链接)列表? 一个链表a某些types的事物List a是空的列表Nil或者一个List a某个元素List a (s的列表)。 在Haskell(我最熟悉的函数式语言)中,我们写了这个

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

所有歧视的工会都是这样定义的:单一types有固定数量的不同方式来创造它; 像NilCons这样的创造者被称为构造者。 这意味着List atypes的值可以用两个不同的构造函数创build – 它可以有两个不同的形状。 所以假设我们想写一个head函数来获取列表的第一个元素。 在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 

由于List a值可以是两种不同的types,我们需要分别处理每一个值。 这是模式匹配。 在head x ,如果x匹配模式Nil ,那么我们运行第一个案例; 如果它匹配模式Cons h _ ,我们运行第二个。

简短的回答,解释:我认为考虑这种行为的最好方法之一是改变你如何看待等号。 在大括号语言中,大体上, =表示赋值: a = b意思是“使a变成b 。然而,在很多函数式语言中, =表示一个相等的断言: let Cons a (Cons b Nil) = frob x 断言左边的东西Cons a (Cons b Nil)等价于右边的东西frob x ; 另外,左侧使用的所有variables都可见。 函数参数也是如此:我们断言第一个参数看起来像是Nil ,如果没有,我们继续检查。

这意味着,而不是写作

 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; }; 

模式匹配有点像类固醇上的重载方法。 最简单的情况与java中所看到的大致相同,参数是具有名称的types列表。 调用的正确方法是基于传入的参数,并且将参数名称分配给这些参数。

模式更进一步,可以进一步解构通过的论据。 它也可能使用警卫实际上根据参数的值进行匹配。 为了演示,我会像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中,它期望一个数组,它分解第二个参数,期望一个具有两个props(prop1,prop2)的对象,并将这些属性的值赋给variablesd和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被限制为types的唯一方法是重载的情况下,模式匹配可以做更多的事情。

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

模式匹配允许您将一个值(或一个对象)与某些模式进行匹配,以select代码的一个分支。 从C ++的angular度来看,它可能听起来有点类似于switch语句。 在函数式语言中,模式匹配可用于匹配标准原始值(如整数)。 但是,它对组合types更有用。

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

 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') } 

第二次使用处理函数数据types,如元组 (允许您将多个对象存储在单个值中)以及区分的联合 ,这些联合可以让您创build可以包含多个选项之一的types。 这听起来有点像enum除了每个标签也可以带有一些值。 在伪C ++语法中:

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

现在, Shapetypes的值可以包含具有所有坐标的Rectangle或包含中心和半径的Circle 。 模式匹配允许您编写使用Shapetypes的函数:

 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) } 

最后,你也可以使用结合了这两个function的嵌套模式 。 例如,您可以使用Circle(0, 0, radius)匹配所有形状的中心点[0,0],并有任何半径(半径的值将分配给新的variablesradius )。

从C ++的angular度来看,这可能听起来有些不太熟悉,但是我希望我的伪C ++能够使解释清楚。 函数式编程基于完全不同的概念,所以它在function语言中更好理解!

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

这是从上面的wikibook一个不错的定义:

因此,模式匹配是一种为事物分配名称的方法(或者将这些名称绑定到这些事物上),并且可能同时将expression式分解为子expression式(就像我们在map定义中的列表那样)。

对于很多人来说,如果提供一些简单的例子,提出一个新的概念就更容易了,所以我们来看看:

假设你有一个三个整数的列表,并且想添加第一个和第三个元素。 没有模式匹配,你可以这样做(Haskell中的例子):

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

现在,尽pipe这是一个玩具的例子,但是想象一下,我们想要将第一个和第三个整数绑定到variables上并对它们进行求和:

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

从数据结构中提取值是模式匹配的function。 你基本上“反映”某种东西的结构,给variables绑定感兴趣的地方:

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

当你用[1,2,3]作为参数调用这个函数时,[1,2,3]将和[first, _ ,third]统一,先绑定到1,third到3,然后丢弃2( _ is你不关心的东西的占位符)。

现在,如果你只想匹配2作为第二个元素的列表,你可以这样做:

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

这只适用于列表中第二个元素为2,否则抛出exception,因为没有定义addFirstAndThird给非匹配列表。

到目前为止,我们只使用模式匹配来解构绑定。 在此之上,你可以给出同一个函数的多个定义,在这个定义中使用了第一个匹配的定义,因此,模式匹配有点类似于“立体匹配上的一个switch语句”:

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

addFirstAndThird将愉快地添加列表的第一个和第三个元素作为其第二个元素,否则“通过”和“返回”0.这种“类似开关”的function不仅可以在函数定义中使用,例如:

 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 

此外,它不仅限于列表,还可以与其他types一起使用,例如匹配Maybetypes的Just和Nothing值构造函数以便“解包”该值:

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

当然,这些只是玩具的例子,我甚至没有给出正式或者详尽的解释,但是他们应该足以把握这个基本概念。

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

它不仅是一个function性的语言function,而且可用于许多不同的语言。

我第一次遇到这个想法的时候,是在我学习了语言真正核心的prolog的时候。

例如

last([LastItem],LastItem)。

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

上面的代码将给出列表的最后一个项目。 input参数是第一个,结果是第二个。

如果列表中只有一个项目,解释器将select第一个版本,第二个参数将被设置为等于第一个值,即将值赋给结果。

如果列表中同时包含头部和尾部,则解释器将select第二个版本并recursion,直到列表中只剩下一个项目。

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

比方说,你想sorting列表中的一个元素:

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

(我已经整理了“纽约”)

 ["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) 

正如你所看到的模式匹配解决scheme噪声较小,你可以清楚地看到有什么不同的情况下,是多么容易的旅行和解构我们的名单。

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