recursion - 在 OCaml 中折叠列表

Question

在 OCaml 中，一个典型的折叠函数如下所示:

let rec fold (combine: 'a -> 'b -> 'b) (base: 'b) (l: 'a list) : 'b =
  begin match l with
  | [] -> base
  | x :: xs -> combine x (fold combine base xs)
  end

对于熟悉 OCaml 的人(不像我)，它的作用应该非常简单。

我正在编写一个函数，当列表中的所有项目都满足条件时返回 true:如果条件 x 对于某个列表 l 中的所有 x 都为真。但是，我正在使用折叠函数实现该函数，但我被卡住了。具体来说，我不知道列表应该返回什么。我知道理想情况下应该将条件应用于列表中的每个项目，但我不知道语法应该是什么样子。 x && acc 有效，但它未能通过非常简单的测试(如下所示)

let test () : bool =
  not (for_all (fun x -> x > 0) [1; 2; -5; -33; 2])
;; run_test "for_all: multiple elements; returns false" test

这是我的初步尝试。任何帮助表示赞赏:

let  for_all (pred: 'a -> bool) (l: 'a list) : bool =
fold (fun(x:'a)(acc: bool)->  _?_&&_?_  )false l

Answer 1

let rec fold (combine: 'a -> 'b -> 'b) (base: 'b) (l: 'a list) : 'b =
  match l with
  | [] -> base
  | x::xs -> combine x (fold combine base xs)

let for_all (pred: 'a -> bool) (lst: 'a list) =
  let combine x accum =
    (pred x) && accum
  in
  fold combine true lst

你的组合函数不应该做 x && base因为列表的元素通常不是 bool .您希望您的谓词函数首先将元素评估为 bool，然后您将其与累加器“和”。

不需要 begin和 end在 fold .您可以使用 match <identifier> with 进行模式匹配.

有两种广泛使用的类型 fold : fold_left和 fold_right .您正在使用 fold_right , 它基本上遍历整个列表并从列表的末尾开始“组合”到前面。这不是 tail-recursive .

fold_left ，另一方面，从列表的前面开始，并立即将每个元素与累加器组合在一起。这不会通过许多递归函数调用“吃掉”您的堆栈。