Почему эта функция SML mergeSort не возвращает отсортированный список?

Question

В итоге ничего не возвращается. Кроме того, при запуске он говорит:

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

Когда я знаю, что это должно быть так:

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

Функция:

fun merge_sort f = 
    let
        fun merge(nil, ylist) = ylist
        |   merge(xlist, nil) = xlist
        |   merge(x::xend, y::yend) =
        if f (x,y) then
            x::merge(xend, y::yend)
        else
            y::merge(x::xend, yend)

        fun split nil = (nil, nil) 
        |   split [x] = ([x], nil)
        |   split (x::y::xy) = 
            let 
                val (low, up) = split xy
            in 
                (x::low, y::up)
            end

    in
        let
            fun real nil = nil
            | real L = 
                let
                    val (list1,list2) = split L
                in
                    merge (real list1,real list2)
            end
        in
             fn last => real last
        end
    end;

 merge_sort (op >) [0, 5, 1, ~4, 9, 11]

Answer 1

Забавный тип на самом деле в некоторой степени связан с ошибкой, из-за которой ваша функция никогда не завершается.

Удаление пользовательского сравнения и разделение помощников (и свертывание merge_sort и real):

fun split nil = (nil, nil) 
  | split [x] = ([x], nil)
  | split (x::y::xy) = 
    let 
        val (low, up) = split xy
    in 
        (x::low, y::up)
    end;

fun merge (nil, ylist) = ylist
  | merge (xlist, nil) = xlist
  | merge (x::xend, y::yend) =
    if x < y then
        x::merge (xend, y::yend)
    else
        y::merge (x::xend, yend);


fun merge_sort nil = nil
  | merge_sort L =
    let
        val (list1,list2) = split L
    in
        merge (merge_sort list1, merge_sort list2)
    end;

мы получаем эти типы:

val split = fn : 'a list -> 'a list * 'a list
val merge = fn : int list * int list -> int list
val merge_sort = fn : 'a list -> int list

и merge_sort берет список чего угодно и выдает int list.
Это странно.
Давайте посмотрим, как это было

fun merge_sort nil = nil

nil может быть списком чего угодно, что дает 'a list -> 'a list.

| merge_sort L =
  let
      val (list1,list2) = split L
  in
      merge (merge_sort list1, merge_sort list2)
  end;

Теперь результат должен быть int list, потому что это то, что merge производит, и это также согласуется с параметрами merge.
Но до сих пор нет способа вывести более конкретный тип c из параметра merge_sort - он только передается обратно merge_sort, а 'a list - это то, что мы уже получили, поэтому в итоге получим 'a list -> int list.

Посмотрим, что произойдет, когда вы сортируете одноэлементный список:

    merge-sort [1]
--> let val (list1, list2) = split [1] in merge (merge_sort list1, merge_sort list2)
--> merge (merge_sort [1], merge_sort [])

и у нас есть рекурсия, которая не заканчивается.

Вам нужен отдельный базовый случай для одноэлементного списка:

| merge_sort [x] = [x]

и когда вы добавляете это, типы должны быть такими.

Answer 2

Поскольку это проблема отладки, вот как я мог бы go найти эту проблему:

Сначала я запускаю программу и понимаю, что она вызывает исключение Out_of_memory. Итак, я знаю, что происходит бесконечная рекурсия. Где-то предполагается, что рекурсивный вызов затрагивает базовый случай, но это не так, и вместо этого он вызывает себя до тех пор, пока не исчерпает память.

Функция состоит из нескольких вспомогательных функций. Посмотрите, все ли они работают по назначению.

Поскольку merge встроен как внутренняя функция merge_sort, его трудно проверить изолированно, потому что вы не можете напрямую обратиться к нему, и если вы двигаетесь его не удается скомпилировать, поскольку он ожидает функцию сравнения f из родительской области видимости. Так что я собираюсь немного изменить merge для целей тестирования.

Функция split не нуждается в аналогичной модификации, а функция real кажется не нужной, поскольку это просто слияние функция сортировки; let внутри let также кажется ненужным, но, поскольку я убираю все вспомогательные функции, они все равно будут удалены как следствие. Поэтому я собираюсь удалить real и просто назвать его mergeSort.

Результат (с некоторым дополнительным переименованием nil в [] и так далее, что является моим предпочтением):

fun merge p ([], ys) = ys
  | merge p (xs, []) = xs
  | merge p (x::xs, y::ys) =
      if p (x,y) then
        x::merge p (xs, y::ys)
      else
        y::merge p (x::xs, ys)

fun split [] = ([], [])
  | split [x] = ([x], [])
  | split (x::y::xys) =
    let
      val (lo, hi) = split xys
    in
      (x::lo, y::hi)
    end

fun mergeSort p [] = []
  | mergeSort p zs =
    let
      val (xs, ys) = split zs
    in
      merge p (mergeSort p xs, mergeSort p ys)
    end

При тестировании все равно выдается ошибка Out_of_memory, поэтому я ничего не исправил.

Давайте попробуем запустить его вручную на небольшом входе;

• Каждая строка, которая начинается с = ниже, обозначает термин перезапись, где я заменил некоторую часть предыдущего выражения его определением. Например, mergeSort (op >) [1,2,3], являющаяся отправной точкой, заменяется определением mergeSort на входе, который соответствует шаблону [1,2,3].
• Каждая строка, начинающаяся с `- это моя попытка раскрыть часть выражения, не включив ее в общую перезапись вышеприведенного выражения - в противном случае это может стать немного грязным.

  mergeSort (op >) [1,2,3]
= let val (xs, ys) = split [1,2,3] in merge (op >) (mergeSort (op >) xs, mergeSort (op >) ys) end
   `-   split [1,2,3]
      = let val (lo, hi) = split [3] in (1::lo, 2::hi) end
      = let val (lo, hi) = ([3], []) in (1::lo, 2::hi) end
      = (1::[3], 2::[])
      = ([1,3], [2])
= let val (xs, ys) = ([1,3], [2]) in merge (op >) (mergeSort p xs, mergeSort p ys) end
= merge (op >) (mergeSort (op >) [1,3], mergeSort (op >) [2])
   `-   mergeSort (op >) [1,3]
      = let val (xs, ys) = split [1,3] in merge (op >) (mergeSort (op >) xs, mergeSort (op >) ys) end
         `-   split [1,3]
            = let val (lo, hi) = split [] in (1::lo, 3::hi) end
            = let val (lo, hi) = ([], []) in (1::lo, 3::hi) end
            = (1::[], 3::hi)
            = ([1], [3])
      = let val (xs, ys) = ([1], [3]) in merge (op >) (mergeSort (op >) xs, mergeSort (op >) ys) end
      = merge (op >) (mergeSort (op >) [1], mergeSort (op >) [3])
         `-   mergeSort (op >) [1]
            = let val (xs, ys) = split [1] in merge (op >) (mergeSort (op >) xs, mergeSort (op >) ys) end
            = let val (xs, ys) = ([1], []) in merge (op >) (mergeSort (op >) xs, mergeSort (op >) ys) end
            = merge (op >) (mergeSort (op >) [1], mergeSort (op >) [])
               `- OOPS!

Я не знаю Я не знаю, заметили ли вы, но в моей попытке вычислить mergeSort (op >) [1] меня очень быстро попросили вычислить mergeSort (op >) [1] как часть его результата. Но сделав это, я быстро сделаю это снова, снова и снова. Таким образом, после запуска функции вручную получается, что бесконечная рекурсия находится в том, что я называю mergeSort, и в том, что ваш код называет real.

Это ошибка в алгоритме, которую можно исправить констатируя что-то о сортировке одноэлементного списка.

---

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

fun merge cmp ([], ys) = ys
  | merge cmp (xs, []) = xs
  | merge cmp (xs as x::xs', ys as y::ys') =
      case cmp (x, y) of
           GREATER => y :: merge cmp (xs, ys')
         | _       => x :: merge cmp (xs', ys)

fun sort cmp [] = []
  | sort cmp [x] = [x]
  | sort cmp xs =
    let
      val ys = List.take (xs, length xs div 2)
      val zs = List.drop (xs, length xs div 2)
    in
      merge cmp (sort cmp ys, sort cmp zs)
    end

fun down LESS = GREATER
  | down GREATER = LESS
  | down EQUAL = EQUAL

(я сохранил ошибку .)

Сортировка целых чисел теперь:

sort (fn (x,y) => down (Int.compare (x,y))) [1,2,3]