Rom*_*man 119 functional-programming terminology pattern-matching
我正在阅读函数式编程,我注意到许多文章都提到模式匹配是函数式语言的核心特性之一.
有人能为Java/C++/JavaScript开发人员解释这是什么意思吗？
Jul*_*iet 131
了解模式匹配需要解释三个部分:
代数数据类型简而言之
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;
}
}
}
因此,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();
}
(几乎总是,ML语言在没有运行时类型测试或强制转换的情况下实现模式匹配,因此C#代码有点欺骗性.让我们把实现细节放在一边,请一些挥手请:))
简而言之,数据结构分解
好的,让我们回到peek方法:
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 ....)
因此,除了将数据结构绑定到变量之外,我们还可以深入研究它.假设我们有一个节点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#或语言中实现类似功能.想想如何在没有运行时的测试和强制转换的情况下完成它.它当然不难,只是繁琐和笨重.并且您没有编译器检查以确保您已涵盖所有案例.
因此,模式匹配可以帮助您以非常方便,紧凑的语法分解和导航数据结构,它使编译器能够检查代码的逻辑,至少是一点点.这真的是一个杀手级的功能.
Ant*_*sky 31
简短回答:模式匹配的产生是因为函数式语言将等号作为等价的断言而不是赋值.
答案很长:模式匹配是一种基于其给定值的"形状"的调度形式.在函数式语言中,您定义的数据类型通常是所谓的区分联合或代数数据类型.例如,什么是(链接)列表？List某种类型的事物的链接列表a是空列表Nil或a Cons在List a(as 的列表)上键入的一些元素.在Haskell(我最熟悉的函数式语言)中,我们写了这个
data List a = Nil
| Cons a (List a)
所有受歧视的联合都是这样定义的:单一类型有不同的方式来创建它; 像这里Nil和Cons这里的创造者被称为构造者.这意味着List a可以使用两个不同的构造函数创建类型的值- 它可以具有两个不同的形状.因此,假设我们想要编写一个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值可以是两种不同的类型,我们需要分别处理每一种; 这是模式匹配.在head x,如果x匹配模式Nil,那么我们运行第一个案例; 如果它匹配模式Cons h _,我们运行第二个.
简短的回答,解释说:我认为考虑这种行为的最好方法之一是改变你对等号的看法.在大括号语言中,大体上=表示赋值:a = b表示"make ainto" b.然而,在许多函数式语言中,=表示相等的断言:let Cons a (Cons b Nil) = frob x 断言左边的东西Cons a (Cons b Nil),等同于on on on on on正确的frob x; 此外,左侧使用的所有变量都可见.这也是函数参数发生的事情:我们断言第一个参数看起来像Nil,如果没有,我们继续检查.
ken*_*ytm 21
这意味着不是写作
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中看到的大致相同,参数是带有名称的类型列表.调用的正确方法基于传入的参数,并且它还可以作为参数名称的参数的赋值.
模式只是更进一步,可以进一步破坏传递的参数.它还可以使用防护来根据参数的值实际匹配.为了演示,我假装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中都有这个.
模式匹配允许您将值(或对象)与某些模式匹配,以选择代码的分支.从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++能够清楚地解释这个问题.函数式编程基于完全不同的概念,因此在函数式语言中更有意义!
模式匹配是您语言的解释器将根据您提供的参数的结构和内容选择特定函数的地方。
它不仅是一种功能语言特性，而且适用于许多不同的语言。
我第一次遇到这个想法是在我学习序言时，它是语言的真正核心。
例如
last([LastItem], LastItem)。
last([Head|Tail], LastItem) :- last(Tail, LastItem)。
上面的代码将给出列表的最后一项。输入 arg 是第一个，结果是第二个。
如果列表中只有一个项目，解释器将选择第一个版本，第二个参数将设置为等于第一个，即一个值将分配给结果。
如果列表有头部和尾部，解释器将选择第二个版本并递归，直到列表中只剩下一项。