SMLNJ插入排序运算符和操作数不同意错误

问题描述

我正在用SML编写插入排序代码，这里是

Im making an insertion sort code in SML, here it is

fun compare(x:real, y:real, F) = F(x, y);
fun isEqual(x:real, y:real) = ((x <= y) andalso (x >= y));

fun rinsert(x: real, [], F) = [x]
    |rinsert(x, (y::ys), F) =
    if isEqual(x, y) then rinsert (x, ys, F)
    else if compare(x, y, F) then x::y::ys
            else y::(rinsert (x, ys, F));

fun rinsort([], F) = []
    |rinsort(x::xs, F) = rinsert(x, (rinsort(xs, F), F));

但是，在运行它时出现此错误

However, on running it i get this error

val isEqual = fn : real * real -> bool
val rinsert = fn : real * real list * (real * real -> bool) -> real list
stdIn:12.27-12.58 Error: operator and operand don't agree [tycon mismatch]
  operator domain: real * real list * (real * real -> bool)
  operand:         'Z * ('Y list * 'X)
  in expression:
    rinsert (x,(rinsort (<exp>,<exp>),F))

我知道rinsort调用的方法不正确，但是我不确定该如何解决.

I understand that rinsort is calling rinsert incorrectly, but I'm not sure how to fix it.

推荐答案

一些一般反馈:

• 函数compare仅用于切换F自变量的顺序，因此您不妨先引用F本身.

• The function compare only serves the purpose to switch the order of the arguments of F, so you might as well just refer to F itself then.

函数isEqual有点不好.由于实物在SML中不是相等类型，尝试避免像那样比较它们.事实证明，为了对实数进行排序，您只需要<=，而不需要=.

The function isEqual is kind of bad. Since reals are not equality types in SML for a reason, try and avoid comparing them like that. It turns out, in order to sort reals, you only need <=, not =.

函数rinsert具有严格的: real类型注释，这是不必要的，因为在将比较运算符F作为参数时，插入排序也可能是通用的(多态的).

The function rinsert has strict : real type annotations that are unnecessary since your insertion sort, in taking the comparison operator F as a parameter, might as well be generic (polymorphic).

您可能想将参数F称为更具描述性的名称，例如cmp，leq或任何其他使您想起其目的的东西.

You might want to call the parameter F something more descriptive, like cmp, leq, or whatever reminds you of its purpose.

下面是一个如何实现插入排序功能的示例:

Here's an example of how one might also make an insertion sort function:

fun sort leq xs =
    let fun insert (x, []) = [x]
          | insert (x, y::ys) =
              if leq (x, y)
              then x::y::ys
              else y::insert (x, ys)
    in List.foldl insert [] xs
    end

其类型为('a * 'a -> bool) -> 'a list -> 'a list.这相当于例如SML/NJ的内置ListMergeSort.sort.我选择sort为咖喱，因为您可能希望通过部分函数应用程序将其专门化，例如，

It has the type ('a * 'a -> bool) -> 'a list -> 'a list. This is comparable to e.g. SML/NJ's built-in ListMergeSort.sort. I've chosen sort to be curried since you might want to specialize it by partial function application, e.g.,

val realsort = sort (op <=) : real list -> real list
val stringsort = sort (op >) : string list -> string list

但是我不让嵌入式帮助器函数insert取消，因为List.foldl接受类型为('a * 'b -> 'b)的函数，即，元组为(x, ys)并返回带有x的修改后的ys插入.

but I've let the embedded helper function insert to be uncurried since List.foldl takes a function with type ('a * 'b -> 'b), i.e., a tuple of (x, ys) and returns a modified ys with x inserted.

您可能要考虑可以测试您的函数进行排序的属性.一个属性可能是排序后的列表中的所有列表元素都按比较运算符leq指定的顺序.

You may want to consider which properties that can test that your function does sort. One property could be that all list elements in the sorted list are in the order specified by the comparison operator leq.

fun sorted_prop _ [] = true
  | sorted_prop _ [_] = true
  | sorted_prop leq (x::y::xs) = leq (x, y) andalso sorted_prop leq (y::xs)

另一个属性可能是未排序列表中的每个元素都存在于已排序列表中.如果您不假定x具有相等类型(''a)，则后一个属性可能很难测试.但是您可以在测试中专门做到这一点.

Another property could be that each element in the unsorted list exists in the sorted list. The latter property may be hard to test if you're not assuming x to have an equality type (''a). But you could do that in the test specifically.

这篇关于SMLNJ插入排序运算符和操作数不同意错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！