12

我需要编写一个函数来获取字符串列表并在列表中找到最大的字符串。问题是它需要使用 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,)

我的解释如下：

- 输入 xs，如果 xs 为空，则返回一个空字符串

- 否则对于 xs 的第一项调用 List.foldl

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

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

但是，它不键入检查。

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

4

1 回答 1

36

因此，对于您发布的代码：

  1. 您不需要空列表的案例。foldl 会为您解决这个问题。只需将 xs 传递给 foldl 而不是 x。
  2. foldl 是咖喱，所以你不应该在参数周围有括号。

除此之外，它实际上看起来是正确的。无论如何，如果您仍然不确定 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
于 2013-02-06T23:08:57.147 回答