recursion - 在 OCaml 中折叠列表
问题描述
在 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
解决方案
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
您的 combine 函数不应该这样做x && base
,因为列表的元素通常不是bool
. 您希望您的谓词函数首先评估要布尔的元素,然后使用累加器“和”它。
不需要begin
and end
in fold
。您可以只使用match <identifier> with
.
有两种广泛使用的fold
:fold_left
和fold_right
. 您正在使用fold_right
,基本上,它会遍历整个列表并从列表的末尾开始“组合”到前面。这不是尾递归的。
fold_left
, 另一方面,从列表的前面开始,并立即将每个元素与累加器结合起来。这不会通过一些递归函数调用“吃掉”你的堆栈。
推荐阅读
- ansible - 如何在 URI 模块 GET 注册循环输出中检索值?
- excel - 自动过滤一张表中的值大于另一张表中的变量
- excel - 按单元格值过滤多个数据透视表相同的工作表
- angular - AWS S3 和 Angular,文件未更新
- javascript - 如何在我的升级系统中识别 GuildMember?
- html - CSS - 如何使我的文本遵循我的边框半径
- php - PHP Post 值为空
- r - 如何让 R 停止将 R 包下载到 onedrive
- sql - 如何在不使用 IF 的情况下创建新表并检查它是否存在(如果存在则删除所有内容)
- kotlin - 如何在 Kotlin 中编写一个打开然后关闭应用程序的测试