OCaml: fold_left，fold_right转换

Question

在http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html中，我们有：

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

List.fold_left f a [b1; ...; bn] is f (... (f (f a b1) b2) ...) bn。

val fold_right : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b

List.fold_right f [a1; ...; an] b is f a1 (f a2 (... (f an b) ...))。不是尾递归的。

问题是如何使用fold_left函数实现“List.fold_right”函数。这就是我在网上找到的答案：

let rec my_fold_left f a l = List.fold_right (fun x g a -> g (f a x)) l (fun x -> x) a;;

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

我第一次写到：

let rec my_fold_left_old f a l = List.fold_right (fun x a -> f a x) l a;;

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

类型检查是正确的，但是my_fold_left_old是错误的，因为它将列表从最后一个元素扫描到第一个元素。

有人能解释上面的函数my_fold_left，List.fold_right只能有3个参数，但是上面的my_fold_left有4个参数吗？

Answer 1

它在奔跑。从本质上说，List.fold_right有一种('a -> 'b -> 'b) -> 'a list -> 'b类型，这个定义将该操作与'b的函数类型一起使用。

如果您用'c -> 'd代替'b，跳过冗余的parens，您可以看到这如何为'b生成“四个参数”：

('a -> 'c -> 'd -> ('c -> 'd)) -> 'a list -> 'c -> 'd

因此，List.fold_right折叠在列表上，生成一个函数，该函数被应用于一个参数以生成最终结果。为了更清楚地说明这一点，让我们用一个命名的临时代码重写它：

 let foldl f init list =
  let fold_result =
    List.fold_right
      (fun elt g acc -> g (f acc elt))
      list
      (fun x -> x) in
  fold_result init