functional-programming - What happens underneath append function?

Question

I got an implementation for append function in OCaml, but it seems confused to me

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

What is the purpose of the fun y in this case ?

Answer 1

的类型append是'a list -> 'a list -> 'a list。您可以将其视为一个接受两个列表并返回一个列表的函数。但是（正如 OCaml 中的惯用语）该函数是使用currying定义的。所以在基本层面上，append获取第一个列表并返回一个类型的函数'a list -> 'a list。返回的函数采用第二个列表并将第一个列表作为前缀（返回结果）。

value是当第一个列表为空时返回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