SML/NJ - 使用 foldr 的一行长度函数

Question

我正在尝试创建一个长度函数，类似于 ML 中已经包含的函数。我的限制是它必须在一行上完成并使用 map、foldl 或 foldr。

现在我的代码行如下所示：

val mylength = foldr ( fn(x,y) => 1+y) 0;

我绝不是 ML 专家，但到目前为止我的推理是这样的：

据我了解，foldr 将从列表中的最后一项开始，将其作为 x 参数传递到我的函数中，并使用 0 作为初始 y 值。然后它应该将 1 添加到 y 值并基本上忽略 x。理论上，我相信这会给我我的总长度。但是我收到以下错误：

 stdIn:136.5-136.37 Warning: type vars not generalized because of
   value restriction are instantiated to dummy types (X1,X2,...)
 val mylength = fn : ?.X1 list -> int

我的大问题是弄清楚如何以可以接受任何类型列表的方式创建此函数。

如果有人能就如何解决这个问题提供一些建议，我将不胜感激，也许我还没有完全理解 ML 的编程风格。

Answer 1

你的函数本质上是正确的。根据您使用的解释器，它会接受或拒绝给定的代码。例如，运行您在 CloudML 上的代码就可以了。为了避免这个问题，而是将其定义为这样的函数：

fun mylength l = foldr ( fn(x,y) => 1+y) 0 l;

华盛顿大学的 Daniel Grossman 在他的一节课中解释说，这个错误与可变引用有关。很遗憾，我记不清他在哪节课上提到过这个了。

同时您可以考虑以下几点：

SML Warning: Type Vars Not Generalized when using Empty Lists or NONE option
Polymorphic function as return value and value restriction in SML
The value restriction

Answer 2

一个稍长的解决方案（我通过思考 map 的相关性得出了这个解决方案）：

fun len xs = (foldr op+ 0 o map (fn x => 1)) xs;

这里o是组合运算符。我想写

val len  = foldr op+ 0 o map (fn x => 1);

以便模仿 Haskell 中流行的那种无点样式，但运行进入与您的原始定义遇到的完全相同的值限制。

Answer 3

给定一些 standard definitions 用于 foldl 和 foldr:

fun foldr f e []      = e
  | foldr f e (x::xr) = f(x, foldr f e xr);

fun foldl f e []      = e
  | foldl f e (x::xr) = foldl f (f(x, e)) xr;

可以手动将您的函数应用到一个短列表，看看术语重写是如何展开的：

foldr (fn(_,y) => 1+y) 0 [5,6,7]
(fn(_,y) => 1+y) (5,foldr (fn(_,y) => 1+y) 0 [6,7])
(fn(_,y) => 1+y) (5,(fn(_,y) => 1+y) (6,foldr (fn(_,y) => 1+y) 0 [7]))
(fn(_,y) => 1+y) (5,(fn(_,y) => 1+y) (6,(fn(_,y) => 1+y) (7,foldr (fn(_,y) => 1+y) 0 [])))
(fn(_,y) => 1+y) (5,(fn(_,y) => 1+y) (6,(fn(_,y) => 1+y) (7,0)))
(fn(_,y) => 1+y) (5,(fn(_,y) => 1+y) (6,1))
(fn(_,y) => 1+y) (5,2)
3

使用 foldr 你可以看到元素 7 首先被解析（它从右到左折叠）并且表达式的长度（因此堆栈内存）按比例增长到列表中。使用 foldl 你可以看到 5 首先被解析（它从左到右折叠）并且表达式的长度是恒定的。在这两种情况下，匿名函数参数的第一部分都被丢弃。

foldl (fn(_,y) => 1+y) 0 [5,6,7]
foldl (fn(_,y) => 1+y) ((fn(_,y) => 1+y)(5, 0)) [6,7]
foldl (fn(_,y) => 1+y) 1 [6,7]
foldl (fn(_,y) => 1+y) ((fn(_,y) => 1+y)(6, 1)) [7]
foldl (fn(_,y) => 1+y) 2 [7]
foldl (fn(_,y) => 1+y) ((fn(_,y) => 1+y)(7, 2)) []
foldl (fn(_,y) => 1+y) 3 []
3

诚然，lambda 使整个事情变得混乱。给定定义

fun plus1(_,y) = 1+y

下面的重写是等效的，但更清晰。

foldr plus1 0 [5,6,7]
plus1 (5, foldr plus1 0 [6,7])
plus1 (5, plus1 (6, foldr plus1 0 [7]))
plus1 (5, plus1 (6, plus1 (7, foldr plus1 0 [])))
plus1 (5, plus1 (6, plus1 (7, 0)))
plus1 (5, plus1 (6, 1))
plus1 (5, 2)
3

foldl plus1 0 [5,6,7]
foldl plus1 (plus1 (5,0)) [6,7]
foldl plus1 1 [6,7]
foldl plus1 (plus1 (6,1)) [7]
foldl plus1 2 [7]
foldl plus1 (plus1 (7,2)) []
foldl plus1 3 []
3

SML/NJ - 使用 foldr 的一行长度函数

SML/NJ - One line length function using foldr

sml

fold

smlnj

ml