PolyML -递归列表排序

Question

我正在尝试检查PolyML中是否对列表进行了排序。该列表不是内置类型，但我将其定义为：

datatype list = empty | cons of int*list; 

我不知道如何同时检查升序和降序，所以现在我将自己限制在升序(欢迎提供更通用解决方案的任何提示！)。

因此，我的方法如下：

local
    fun sortedIncreasing (empty) = 1000
    |   sortedIncreasing (cons(v,l)) = if(v < sortedIncreasing(l)) then v else Int.minInt
in
    fun isSortedInc (empty) = true
    |   isSortedInc (cons(v,l)) = if (sortedIncreasing(cons(v,l)) = Int.minInt) then false else true
end;   

首先，Int.minInt不是Int类型，所以我有一个类型不匹配。我该怎么解决这个问题呢？

其次，我担心这种方法太幼稚了，我该如何更好地解决这个问题呢？

感谢您的宝贵时间，祝您有愉快的一天！

Answer 1

这个问题可以使用一种更通用的方法来解决，通过这种方法，sorted函数接受一个比较器作为参数。

其可能的实现可能如下所示：

fun sorted comp empty = true
  | sorted comp (cons(x,empty)) = true
  | sorted comp (cons(x,cons(y,xs))) =
        (comp (x,y)) andalso (sorted comp (cons(y,xs)));

通过这种方式，您可以检查列表是否按照比较器定义的任意顺序排序。例如，您可以将函数sortedIncreasing定义为：

val sortedIncreasing = sorted op<=;

下面是一个完整的可运行示例来演示这一点：

datatype mylist = empty | cons of int * mylist;

fun sorted comp empty = true
  | sorted comp (cons(x,empty)) = true
  | sorted comp (cons(x,cons(y,xs))) =
        (comp (x,y)) andalso (sorted comp (cons(y,xs)));

fun fromList [] = empty
  | fromList (x::xs) = cons(x, fromList xs);

val a = fromList [1,2,3,4,5,6];
val b = fromList [6,5,4,3,2,1];
val c = fromList [1,3,2,4,5,6];

val sortedIncreasing = sorted op<=;
val sortedDecreasing = sorted op>=;

sortedIncreasing a; (* val it = true: bool *)
sortedDecreasing a; (* val it = false: bool *)
sortedIncreasing b; (* val it = false: bool *)
sortedDecreasing b; (* val it = true: bool *)
sortedIncreasing c; (* val it = false: bool *)
sortedDecreasing c; (* val it = false: bool *)