append函数下面发生了什么？

Question

我在OCaml中得到了append函数的一个实现，但它似乎让我感到困惑

let rec append = function
| [] -> fun y -> y
| h :: t -> fun y -> h :: (append t y)

在这种情况下，fun y的用途是什么？

Answer 1

append的类型为'a list -> 'a list -> 'a list。您可以将其视为一个接受两个列表并返回一个列表的函数。但是(在OCaml中是惯用的)该函数是使用currying定义的。因此，在基本级别上，append接受第一个列表并返回一个'a list -> 'a list类型的函数。返回的函数接受第二个列表，并在其前面加上第一个列表(返回结果)。

值fun y -> y是append在第一个列表为空时返回的函数。如果你仔细想想，这是有道理的。如果第一个列表为空，则第二个列表将原封不动地返回。换句话说，返回的函数与标识函数(专门应用于列表)没有任何不同。

第二种情况返回值fun y -> h :: (append t y)。这是相似的，但更复杂一点。返回的函数需要做一些实际的附加操作。它通过(递归地)将提供的第二个列表(y)附加到第一个列表(t)的尾部，然后将第一个列表(h)的头部添加到第一个列表的前面。

Answer 2

如果您不喜欢fun，可以像这样重写函数

let rec append x y = match x with
| [] -> y
| h :: t -> h :: append t y