标准ML多态排序

Question

我对ML毫无经验，而且我无法理解这一点。

开始问题

多态性排序

列表上执行插入排序此函数采用作为参数的比较功能较少和元素的列表升进行排序。该代码编译并运行正常：

fun sort(less, nil) = nil | 
    sort(less, a : : l) = 
     let 

fun insert(a, nil) = a : : nil | 
    insert(a, b : : l) = if less(a,b) then a : : (b: : l) 
            else b : : insert(a, l) 

in 
    insert(a, sort(less, l)) 
end; 

这是什么类型的函数的类型？简要解释一下，包括辅助功能插入的类型。您不必在此代码上运行ML算法;只是解释一个普通的ML程序员为什么期望代码具有这种类型。 （结束问题）

我已经得到了排序函数的类型（通过在SML解释器中运行代码），但我无法得到有关插入的第二部分。

类型排序功能：

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

任何帮助将不胜感激。

Answer 1

通过“作弊”算出sort的类型使得下一步更难;不要采取捷径。
（没有人通过在回答偷看学到了什么）

但这里是你如何能想出insert：

你知道从

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

的第二个参数sort是'a list 。

在

insert(a, sort(less, l)) 

，你可以立即看到它有一些X，Y，并且Z某种类型(X * Y) -> Z。

您正在传递sort的第二个参数的第一个元素 - a - 作为insert的第一个参数。
由于sort的第二个参数是'a list，该列表的第一个元素是'a。
所以X是'a，我们现在知道，insert是('a * Y) -> Z为一些Y和Z。

insert的第二个参数的类型 - sort(less, l) - 是众所周知的;它是'a list。
所以我们现在知道，Y是'a list和insert是('a * 'a list) -> Z为一些Z。

所有这一切仍然是返回类型，因为

insert(a, sort(less, l)) 

是什么sort回报，它必须具有相同的返回类型为sort。
所以Z是'a list。

综上所述，insert的类型是

('a * 'a list) -> 'a list