functional-programming - 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) 放在前面。