在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：如果对于在某个列表l中的每个x都满足条件x，则为真。但是，我正在使用fold函数实现该函数，但我被卡住了。具体来说，我不知道列表应该返回什么。我知道理想情况下，应该将条件应用于列表中的每个项目，但我不知道语法应该是什么样子。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

- J_code

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 类型。您需要先将谓词函数评估为布尔值，然后再将其与累加器进行“and”操作。

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

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

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

- Ulugbek Abdullaev

Answer 2

你的fold运行得很好。

但是你对for_all应该如何工作的前提有误。你从初始值false开始，但是for_all是检查每个元素是否满足条件。它只需要找到一个不满足条件的元素就知道整个结果为假。

在每次迭代调用中，如果累加器已经是false，我们知道可以直接将其传播到fold的末尾。如果是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

- Chris