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

小开

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

这是上面维基百科给出的一个很好的定义:

所以模式匹配是一种为事物命名(或绑定) 这些东西的名字) ，和可能会分解表达式同时转换成子表达式 (正如我们在地图定义)。

小开

模式匹配是语言的解释器根据你给出的参数的结构和内容来选择一个特定的函数。

它不仅是一个函数式语言特性，而且可用于许多不同的语言。

我第一次接触到这个想法是在我学习序言的时候，它是语言的核心。

例如:。

最后([ LastItem ] ，LastItem)。

最后([头部 | 尾部] ，最后一项) :- 最后(尾部，最后项目)。

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

如果列表中只有一个条目，解释器将选择第一个版本，并将第二个参数设置为等于第一个，即为结果赋值。

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

小开

对于很多人来说，如果提供一些简单的例子，学习一个新概念会更容易，所以我们开始吧:

假设您有一个包含三个整数的列表，并且希望添加第一个和第三个元素。如果没有模式匹配，你可以这样做(例如在哈斯克尔) :

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

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

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

这种从数据结构中提取值的模式匹配就是这样做的。你基本上是“镜像”了某个东西的结构，为感兴趣的地方提供变量来绑定:

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

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

现在，如果您只想将 list 与2作为第二个元素进行匹配，那么可以这样做:

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

这只适用于2作为第二个元素的列表，否则抛出异常，因为没有为不匹配的列表给出 addFirstAndThird 的定义。

到目前为止，我们只在解构绑定时使用模式匹配。除此之外，你可以给出同一个函数的多个定义，其中使用了第一个匹配定义，因此，模式匹配有点像“关于立体视图的开关语句”:

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

AddFirstAndThird 将很高兴地添加 list 的第一个和第三个元素，并将2作为第二个元素，否则将添加“ fall through”和“ return”0。这种“类开关”功能不仅可以用于函数定义，例如:

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

此外，它不限于列表，但也可以与其他类型一起使用，例如，匹配“也许”类型的 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

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

小开

这意味着，不是写作

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

小开

简短的回答: 模式匹配之所以出现，是因为函数式语言把等号当作 等同的断言等同的断言，而不是赋值。

长话短说: 模式匹配是一种基于所给价值的分派形式。在函数式语言中，定义的数据类型通常称为有区别的联合或代数数据类型。例如，什么是(链接)列表？a类型的事物的链表 List是空列表 Nil或 a Cons类型的某个元素附加到 List a(a的列表)上。在哈斯克尔(我最熟悉的函数式语言) ，我们这样写

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

所有有区别的联合都是这样定义的: 一个类型有固定数量的不同方法来创建它; 创建者，比如这里的 Nil和 Cons，被称为构造函数。这意味着 List a类型的值可以用两个不同的构造函数创建，它可以有两个不同的形状。假设我们想编写一个 head函数来获取列表的第一个元素。在哈斯克尔，我们会这样写

-- `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值可以是两种不同的类型，所以我们需要分别处理每一个值，这就是模式匹配。在 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; 此外，左边使用的所有变量都变得可见。函数参数也是这样: 我们断言第一个参数看起来像 Nil，如果不像，我们继续检查。

小开

模式匹配允许你根据一些模式匹配一个值(或一个对象)来选择代码的一个分支。从 C + + 的角度来看，它可能听起来有点类似于 switch语句。在函数式语言中，模式匹配可以用来匹配标准的基元值，例如整数。但是，它对于组合类型更有用。

首先，让我们演示一下基本值的模式匹配(使用扩展的伪 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') }

第二种用法处理功能性数据类型，例如元组(它允许您在单个值中存储多个对象)和 受歧视的工会，它允许您创建一个可以包含多个选项之一的类型。这听起来有点像 enum，除了每个标签也可以携带一些值。在伪 C + + 语法中:

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

类型为 Shape的值现在可以包含具有所有坐标的 Rectangle或具有中心和半径的 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 + + 能够解释清楚。函数式编程基于完全不同的概念，所以它在函数式语言中更有意义！

小开

模式匹配就像是类固醇过载的方法。最简单的情况与你在 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 是一个数组，它分解第二个参数，期望一个具有两个道具(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 仅限于类型作为重载的唯一手段时，模式匹配可以做得更多。

除了这里展示的函数重载，同样的原则也可以应用到其他地方，比如案例陈述或解构分配。JavaScript 甚至在1.7中也有这个功能.

小开

最佳答案

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

代数数据类型。

模式匹配是什么

太棒了。

简而言之就是代数数据类型

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

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

定义了一个类似堆栈的数据结构:

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

因此，Cons和 Nil标识符定义了一个简单的类，其中 of x * y * z * ...定义了一个构造函数和一些数据类型。构造函数的参数是未命名的，它们由位置和数据类型标识。

您创建的 a 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()))));

简而言之就是模式匹配

模式匹配是一种类型测试。假设我们创建了一个类似上面这样的堆栈对象，我们可以实现如下方法来查看和弹出堆栈:

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

(几乎总是，机器学习语言实现模式匹配的没有运行时类型测试或强制转换，所以 C # 代码有些欺骗性。让我们用一些手势来刷一下实现细节:)

概括地说就是数据结构分解

好吧，让我们回到偷看的方法:

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

诀窍是理解 hd和 tl标识符是变量(因为它们是不可变的，所以它们不是真正的“变量”，而是“值”;)。如果 s具有 Cons类型，那么我们将从构造函数中提取它的值，并将它们绑定到名为 hd和 tl的变量。

模式匹配是有用的，因为它可以让我们通过它的形状而不是它的内容来分解一个数据结构。想象一下，如果我们定义一个二叉树如下:

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

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

为了进行比较，我们将上面的方法用 C # 编写为:

public abstract class Tree<T> { public abstract U Match(Func nilFunc, Func<Tree<T>, T, Tree<T>, U> nodeFunc); public class Nil : Tree<T> { public override U Match(Func 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(Func 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 # 中实现一些模式匹配，但是由于你不能有效地分解复杂的数据结构，所以它的灵活性就没那么高了。此外，如果你使用的是模式匹配，ABc2。多棒啊？

想想如何在没有模式匹配的情况下用 C # 或其他语言实现类似的功能。考虑一下，如果没有运行时的测试和强制转换，您将如何做到这一点。它当然不是用力，只是笨重和笨重。而且你没有编译器来检查你是否覆盖了所有的情况。

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

小开

下面是一个非常简短的例子，它展示了模式匹配的实用性:

假设您想对列表中的一个元素进行排序:

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

由于您可以看到模式匹配的解决方案具有较少的噪音，因此您可以清楚地看到不同的情况，以及旅行和解构我们的列表是多么容易。

我已经写了一篇关于它的更详细的博客文章给你。