polymorphism - SML NJ - 多态自定义列表类型并对元素求和

Question

我正在学习多态性和 SML。我有点不确定如何在保持函数多态性的同时处理元素的求和。

如果我有这个定义...

datatype 'a customList = nothing | customL of 'a * 'a customList

还有这个列表...

val a = customL(2, customL(1, customL(3, nothing)))

我认为由于多态处理，我需要使用 (op +)，但我无法让它们工作......

fun addElements (op +) nothing = 0
|   addElements (op +) (customL(x, nothing) = x
|   addElements (op +) (customL(x, xs)) = x + addElements xs

我还认为处理“无”也可能会弄乱类型？

有人可以帮助让这个工作吗？

更新

我想我已经接近它了，但我不明白为什么我会收到错误......

exception EmptyList

fun addElements (op + ) nothing = raise EmptyList
|   addElements (op + ) (customL(x, nothing)) = x
|   addElements (op + ) (customL(x, xs)) = let val rest_of_list = addElements (op +) xs
                                       in
                                          (op + ) (x, rest_of_list)
                                       end

Answer 1

你所拥有的东西有效，但我不认为它能起到你认为的作用。例如，

addElements (op - ) customL(2, customL(1, customL(3,nothing)))

评估结果为 4，并且

addElements (fn (x,y) => x) customL(2, customL(1, customL(3,nothing)))

计算结果为 2。

要查看发生了什么，请暂时忘记 customL。该定义很好，但与 list 同构，因此要查看 addElements 发生了什么，用普通列表编写它不会分散注意力:

fun addElements (op + ) [] = raise Empty
|   addElements (op + ) [x] = x
|   addElements (op + ) (x::xs) = (op +)(x, addElements (op +) xs);

这基本上就是您所拥有的，只不过它使用模式匹配而不是 let 绑定(bind)。 SML 将此视为:

val addElements = fn : ('a * 'a -> 'a) -> 'a list -> 'a 

请注意，类型与加法或偶数(整数或实数)无关。

发生的情况是您在定义正文中重新定义 (op +)。 SML 大量使用预定义标识符，而不是保留名称。这种区别看起来很迂腐，但这意味着您可以自由地重新定义任何东西:

val (op + ) = 5;
(op + ) * 7;

评估结果为 35。

在定义主体中(op +)可以是'a * 'a -> 'a类型的任何函数。因此，使用符号 + 和名称 addElements 会产生误导。最能说的是它反射(reflect)了您的意图，但我不认为这是重新定义内置运算符的充分理由，即使在本地范围内也是如此。

定义函数的误导性较小的方法应该是:

fun combineElements combiner [] = raise Empty
|   combineElements combiner [x] = x
|   combineElements combiner (x::xs) = combiner (x,combineElements combiner xs);

这里名称的选择清楚地表明它是一个多态函数，它使用有序对上的函数将列表组合为单个项目。

SML 有一个标准函数 foldl，它可以完成所有这些工作，甚至更多:

- foldl (op + ) 0 [1,2,3];
val it = 6 : int
- foldl (op + ) 0.0 [1.0, 2.0, 3.0];
val it = 6.0 : real
- foldl (op +) 0 [];
val it = 0 : int

请注意，它可以处理空列表。这就是我在评论中评论时所想到的，您似乎正在尝试做一种折叠，但您希望在选择加法作为运算符时进行硬连线。