0

我试图检查列表是否在 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，所以我有一个类型不匹配。我怎么能解决这个问题？
其次，我担心这种方法很幼稚，我该如何以更好的方式解决问题？

感谢您的时间，祝您有美好的一天！

4

1 回答 1

0

这个问题可以使用更通用的方法来解决，其中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 *)
于 2019-11-11T14:22:59.327 回答