recursion - 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 称为 as 模式。它允许我们:

1. 针对非空列表进行模式匹配，其中 x 是列表的头部，l 是列表的尾部
2. 用名称L引用整个匹配列表x::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::l as 模式相对于 non as 模式的最大优势是它允许我们引用整个列表，而不仅仅是它的头和尾，并且当我们需要引用整个列表时，避免了额外的列表构造。请注意，这两段代码的唯一区别是 n::L 和 n::x::l。由于我们在第一个 insert 函数中使用了 as 模式 L as x::l，所以我们能够执行 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，因此这两个作为模式是不必要的。