了解ML中的foldl

Question

我需要编写一个函数,它接受一个字符串列表并找到列表中最大的字符串.问题是它需要使用List.foldl迭代列表,并且不能使用递归调用,除了List,foldl的库函数中的那些调用.

我写

fun longest_string1(xs)= 
case xs of 
[] => ""  
| x::xs' => List.foldl((fn (s,x) => if String.size s > String.size x then s else x) "" x,)

我的解释如下:

-s in xs,如果xs为空则返回一个空字符串 -

另外xs调用的第一项List.foldl

-List.foldl传入一个匿名函数来检查s的长度,这应该是表示针对列表的head项的累加器.

- 将初始累加器设置为空字符串,将初始比较值设置为高阶函数传入的初始列表的头部

但是,它不进行类型检查.

我认为我的问题在于理解List.foldl函数本身以及它如何读取其参数.有人可以提供一些澄清吗？

Answer 1

那么,对于您发布的代码:

1. 您不需要空列表的大小写.foldl会照顾你.只需将xs传递给foldl而不是x.
2. foldl是curried,所以你不应该在参数周围加上括号.

除此之外,它实际上看起来是正确的.无论如何,如果你仍然不确定foldl是如何工作的,这里有一个非常详尽的解释;)

好的,让我们从List.foldl开始.

val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

所以,有三个参数.一个是我们稍后会担心的函数,第二个是与返回类型相同类型的值,最后一个是列表.

所以,让我们举一个简单的例子 - 比如我们有一个整数列表,我们想要总结所有数字.我们可以这样做:

fun sum [] = 0
  | sum (x::xs) = x + sum xs

或者,我们可以使用foldl(从现在起我会写foldl而不是List.foldl,因为我很懒).

所以,我们知道列表是第三个参数.第二个应该是某种起始值,或累加器,如果列表为空则有意义.总和,那将是0.

第一个参数是一个函数,这是棘手的部分.类型是:

fn : 'a * 'b -> 'b

好的,所以'a也是列表中元素的类型,所以如果这是列表中的项目则有意义.'b是起始值和返回值的类型.

实际发生的是foldl使用列表中的第一个元素和累加器调用函数.然后它将结果称为新累加器,以及列表的其余部分.所以,如果我们这样做:

foldl foo 0 [1,2,3]

它会的

foo (1,0)

然后

foldl foo (foo (1,0)) [2,3]

等等.

因此,对于汇总列表,我们将进行以下功能:

fn (x,acc) => x + acc

所以我们可以这样做:

fun sum xs = foldl (fn (x,acc) => x + acc) 0 xs

或者,甚至更简单

val sum = foldl op+ 0

(op+与我之前使用的匿名函数相同)

让我们通过列表来完成它 [1,2,3]

foldl op+ 0 [1,2,3]
foldl op+ (op+ (1,0)) [2,3] -> foldl op+ 1 [2,3]
foldl op+ (op+ (2,1)) [3]   -> foldl op+ 3 [3]
foldl op+ (op+ (3,3)) []    -> foldl op+ 6 []
6