在 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。您希望谓词函数首先计算要布尔的元素，然后使用累加器"和"它。

fold不需要begin和end.您可以只与match <identifier> with进行模式匹配。

有两种普遍的fold类型：fold_left和fold_right。您正在使用fold_right，基本上，它会遍历整个列表并开始从列表末尾"组合"到前面。这不是尾递归。

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

Answer 2

您的fold工作正常。

但是你是在关于for_all应该如何工作的错误的前提下运作的。您从false上的初始值开始，但for_all检查条件是否适用于每个元素。它只需要找到一个不成立的元素，就知道整个事情都是假的。

在每次迭代调用中，如果累加器已经false我们知道我们可以将其传播到折叠的末尾。如果为 true，我们将累加器更新为在当前值上调用谓词的结果。

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