SML foldl函数 - 添加到具有条件的列表中

Question

我有一个关于函数式编程的大学课程,我使用SML.作为考试的准备,我正在研究一些没有解决方案的旧考试.

我真正遇到问题的唯一问题之一是使用以下问题foldl:

考虑程序骨架:fun addGt k xs = List.foldl(...)... xs; 填写两个缺失的部分(由点......表示),这样addGt k xs是xs中那些大于k的元素的总和.例如,addGt 4 [1,5,2,7,4,8] = 5 + 7 + 8 = 20

我确信这很简单,但我很难理解foldl和foldr函数.

我现在有以下内容(如果你问我的编译器,这似乎是非常错误的!):

fun addGt(k,xs) = List.foldl ( fn x => if x > k then op+ else 0) 0 xs;

我真的很感激这个问题的一些帮助,也许是一个非常简短的评论,可以说明foldl和foldr功能!

非常感谢.

Answer 1

我只是解决了以下问题:

fun addGt(k, xs) = List.foldl (fn (x, y) => if x >= 5  then x + y else y) 0 xs;

但让我解释一下.首先检查List.foldl函数的类型,它是:

('a * 'b -> 'b) -> 'b -> 'a list -> 'b

因此List.foldl是一个curried函数,它将第一个参数作为类型的另一个函数('a * 'b -> 'b).你用的是(fn x => if x > k then op+ else 0)哪种类型int -> int.你应该提供List.foldl一个带有类型元组int * int并返回一个元组的函数,int如下所示:(fn (x, y) => do stuff).这就是为什么你的代码没有编译,你传递了错误的函数类型foldl.

现在你可以这样思考foldl:

foldl f b [x_1, x_2, ..., x_(n - 1), x_n] = f(x_n, f(x_(n - 1), ..., f(x2, f(x1, b)) ...))where f是函数类型('a * 'b -> 'b),类型b是什么,'b列表[x_1, x_2, ..., x_(n - 1), x_n]是类型'a list.

类似的foldr你可以这样想:

foldr f b [x_1, x_2, ..., x_(n - 1), x_n] = f(x_1, f(x_2, ..., f(x_(n - 1), f(x_ n, b))