SMLNJ Оператор сортировки вставками и операнд не согласуются с ошибкой

Если это может быть полезно, это пример того, как ваш код должен работать с areal list:

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);

val funcComp = fn r1 : real => fn r2 : real => if r1 < r2 then true else false;
val l : real list = [1.0, 3.8, 5.6, 3.8, 4.4, 5.6, 6.3, 5.5, 4.6, 8.1];
val b = rinsort(l, funcComp);

Некоторые общие отзывы:

• Функция compare служит только для переключения порядка аргументов F, поэтому вы можете просто обратиться к самой F.

• Функция isEqual немного плохая. Поскольку reals не являются типами равенства в SML по какой-то причине, постарайтесь не сравнивать их так. Оказывается, для сортировки реалов нужно только <=, а не =.

• Функция rinsert имеет строгие аннотации типа : real, которые не нужны, поскольку ваша сортировка вставками, принимая оператор сравнения F в качестве параметра, также может быть универсальной (полиморфной).

• Возможно, вы захотите назвать параметр F как-то более описательно, например, cmp, leq или как-то так, что напоминает вам о его назначении.

Вот пример того, как можно сделать функцию сортировки вставками:

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. Это сравнимо, например, с Встроенная функция ListMergeSort.sort SML/NJ. Я выбрал sort как каррированный, поскольку вы можете захотеть специализировать его с помощью применения частичных функций, например,

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

но я позволил встроенной вспомогательной функции insert быть некаррированной, так как List.foldl принимает функцию с типом ('a * 'b -> 'b), т. е. кортеж (x, ys), и возвращает модифицированный ys со вставленным x.

Вы можете рассмотреть, какие свойства могут проверить, что ваша функция выполняет сортировку. Одним из свойств может быть то, что все элементы списка в отсортированном списке находятся в порядке, указанном оператором сравнения 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). Но вы могли бы сделать это специально в тесте.