SML中的模式匹配 - 将列表表示为(x :: y)

Question

我刚开始学习函数式编程,我发现自己对模式匹配的概念非常困惑(我使用的是SML).以下面的表达式为例,在有序列表中插入一个元素:

fun insert (n,nil) = [n]
  | insert (n, L as x::l) =
    if(n < x) then n::L
    else x::(insert(n,l))

如何将列表L表示为x :: l？我知道x指的是列表的第一个元素,l指的是其余部分,但我不知道该怎么称呼它或如何使用它.我已经阅读了很多,但我找到的所有文档都没有提到这一点.这是另一个不使用'as'关键字的示例.

(*returns a list with the sum of each element added of two lists added together*)

fun addLists (nil,L) = L
| addLists (L,nil) = L
| addLists (x::xs,y::ys) =
  (x + y)::(addLists(xs,ys))

谢谢您的帮助!

Answer 1

对于insert这里的功能:

fun insert (n,nil) = [n]
  | insert (n, L as x::l) =
    if(n < x) then n::L
    else x::(insert(n,l))

该| insert (n, L as x::l)部分是一个将被匹配的模式.L as x::l被称为模式.它允许我们:

1. 模式匹配非空列表,其中x是列表的头部,并且l是列表的尾部
2. 请参阅整个匹配列表x::l的名称L

这与做的类似(尽管不完全相同):

  | insert (n, x::l)

除非如果你这样做,该insert功能将变为:

fun insert (n,nil) = [n]
  | insert (n, x::l) =
    if(n < x) then n::x::l
    else x::(insert(n,l))

因此,使用L as x::las模式而不是非模式的最大优点是它允许我们引用整个列表,而不仅仅是它的头部和尾部,并且当我们需要引用整个列表时避免额外的列表构造.观察到2段代码的唯一区别是n::L和n::x::l.因为我们L as x::l在第一个insert函数中使用as模式,所以我们可以n::L代替n::x::l.这避免了一个::操作(也称为cons操作).

至于这个:

fun addLists (nil,L) = L
| addLists (L,nil) = L
| addLists (x::xs,y::ys) =
  (x + y)::(addLists(xs,ys))

对于第二种模式| addLists (x::xs,y::ys),我们无处可重构列表,x::xs并y::ys在其后的代码中,因此我们不需要作为模式.你可以这样写:

fun addLists (nil,L) = L
| addLists (L,nil) = L
| addLists (ListX as x::xs, ListY as y::ys) =
  (x + y)::(addLists(xs,ys))

并且它仍然可以工作,除了我们没有引用ListX或ListY在这里,因此这两个模式是不必要的.