在 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 都为 true。然而，我正在使用折叠函数来实现该函数，但我陷入了困境。具体来说，我不知道列表应该返回什么。我知道理想情况下该条件应该应用于列表中的每个项目，但我不知道语法应该是什么样子。

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

，它基本上会遍历整个列表并开始从列表末尾到前面“组合”。这不是“尾递归”。 另一方面，

fold_left

从列表的前面开始，立即将每个元素与累加器组合起来。这不会因多次递归函数调用而“吃掉”您的堆栈。

Answer 2

fold

工作正常。

但是您对于

for_all

应该如何运作的前提是错误的。您从

false

上的初始值开始，但

for_all

正在检查每个元素的条件是否成立。它只需要找到

one

不成立的元素就可以知道整个事情都是假的。 在每次迭代调用中，如果累加器已经是

false

，我们知道我们可以将其传播到折叠的末尾。如果为真，我们将累加器更新为对当前值调用谓词的结果。

let for_all predicate lt =
  fold (fun x acc -> if not acc then acc else predicate x) true lst

这本质上是一种低效的实现方式 

for_all

因为即使第一次迭代返回

false

我们仍然必须遍历整个列表。通过在没有

fold

的情况下编写此代码，我们可以在找到

false

条件后立即退出递归。

let rec for_all predicate = function
  | [] -> true
  | x::_ when not (predicate x) -> false
  | _::xs -> for_all predicate xs