我需要使用折叠器找到列表的最小值。
这是我写的代码：
fun minlist nil = nil
| minlist (x::xs) = List.foldr (fn (y,z) => if y < z then y else z) x xs;
但是我收到一个错误："重载>不能应用于类型为"列表"的参数">
我已经卡了一段时间了。任何帮助不胜感激
您的第一个子句说空列表的最小值是一个列表。
因此，(fn (y,z) => if y < z then y else z)生成一个列表，y和z也必须是列表。
对于空列表，您无法生成合理的值，因此您应该删除该情况并接受编译警告，或者引发异常。
查找两个值的最小值
表达式if y < z then y else z具有内置名称Int.min (y, z)。
处理空列表
您将空列表处理为minlist nil = nil，这意味着"空 int 列表的最小 int 是空列表"。但是空列表不是 int，因此不能是 int 列表中的元素，也不能是返回最小 int 的函数的返回值。
正如 molbdnilo 所说，您可以忍受编译警告(如果您曾经向函数提供空列表，则可能会在运行时引发Match异常)，或者在给定空列表时引发特定异常，例如Empty。两者都不好，但后者至少使问题变得清晰。
在不foldr的情况下编写此内容可能如下所示：
fun minimum [] = raise Empty
| minimum [x] = x
| minimum (x::xs) = Int.min (x, minimum xs)
将递归函数转换为折叠
给定一些递归函数foo依赖于某些函数bar和某些默认值acc：
fun foo [] = acc
| foo (x::xs) = bar (x, foo xs)
您可能会注意到minimum和foo之间的相似之处：
acc是x，一些最小值barInt.min.
这是试图推广minimum的递归方案。
给定函数foldr：
fun foldr f e [] = e
| foldr f e (x::xs) = f (x, foldr f e xs);
您可能会注意到相同的相似之处：
f是bar，但被制作成参数e是acc，但被做成一个参数
minimum中唯一不符合此一般递归方案的是处理空列表。所以你仍然必须与foldr分开来做：
fun minimum [] = ...
| minimum (x::xs) = foldr ...
但其余的都差不多。
错误感知返回类型
第三种选择是将函数的类型签名更改为
val minimum : int list -> int option
您当前的练习可能不允许。
在不foldr的情况下编写此内容可能如下所示：
fun minimum [] = NONE
| minimum [x] = SOME x
| minimum (x::xs) =
case minimum xs of
NONE => SOME x
| SOME y => SOME (Int.min (x, y))
或者更好的是：
fun minimum [] = NONE
| minimum [x] = SOME x
| minimum (x::xs) = Option.map (fn y => Int.min (x, y)) (minimum xs)
将此函数转换为使用foldr的过程相同，但f不同
尾递归
不折叠的minimum函数(从上面重复)：
fun minimum [] = raise Empty
| minimum [x] = x
| minimum (x::xs) = Int.min (x, minimum xs)
有一个问题是它主要使用堆栈内存。
这可以通过手动评估函数来说明：
minimum [1,2,3,4,5]
~> Int.min (1, minimum [2,3,4,5])
~> Int.min (1, Int.min (2, minimum [3,4,5]))
~> Int.min (1, Int.min (2, Int.min (3, minimum [4,5])))
~> Int.min (1, Int.min (2, Int.min (3, Int.min (4, minimum [5]))))
~> Int.min (1, Int.min (2, Int.min (3, Int.min (4, 5))))
~> Int.min (1, Int.min (2, Int.min (3, 4)))
~> Int.min (1, Int.min (2, 3))
~> Int.min (1, 2)
~> 1
由于在递归调用返回之前无法计算外部Int.min，因此用于计算函数的堆栈内存量与列表的长度成正比。
您可以通过使用累积参数来避免这种情况：
fun minimum [] = raise Empty
| minimum (y::ys) =
let fun helper [] acc = acc
| helper (x::xs) acc = helper xs (Int.min (x, acc))
in helper ys y end
手动评估此功能：
minimum [1,2,3,4,5]
~> helper [2,3,4,5] 1
~> helper [3,4,5] (Int.min (2, 1))
~> helper [3,4,5] 1
~> helper [4,5] (Int.min (3, 1))
~> helper [4,5] 1
~> helper [5] (Int.min (4, 1))
~> helper [5] 1
~> helper [] (Int.min (5, 1))
~> helper [] 1
~> 1
由于Int.min是可交换的，因此您不妨用foldl而不是以与上面完全相同的方式foldr来解决此练习，并且您将拥有一个使用更少堆栈空间的尾递归变体。