Функция SML merge_sort, использующая пропуск и сопоставление с образцом - PullRequest
Новая
       24

Функция SML merge_sort, использующая пропуск и сопоставление с образцом

0 голосов
/ 27 февраля 2020 
fun merge_sort (_, nil) = nil
  | merge_sort (_, [a]) = [a]
  | merge_sort (f, L)   =
    let
        fun halve nil = (nil,nil)
          | halve [a] = ([a], nil)
          | halve (a :: b :: rest) =
            let
                val (x , y) = halve rest
            in
                (a :: x, b :: y)
            end
        fun merge (f, nil, x) = x
          | merge (f, x, nil) = x
          | merge (f, a::b, x::y) =
            if f(a, b) then a :: merge (f, b, x::y)
                       else x :: merge (f, a::b, y);
        val (x, y) = halve L
    in
        merge(f, merge_sort(f, x), merge_sort(f,y))
    end;

merge_sort (op <) [2,1,3,2,4,3,45];

Это функция SML, над которой я работал. Он предназначен для вызова функции, как показано внизу, и сортировки слиянием. Должна быть одна функция. Я изо всех сил пытаюсь понять сопоставление с образцом и как полностью заставить эту функцию работать.

Я получаю этот код ошибки при компиляции и запуске. 

$sml < main.sml
Standard ML of New Jersey v110.78 [built: Thu Aug 31 03:45:42 2017]
- val merge_sort = fn : ('a * 'a list -> bool) * 'a list -> 'a list
stdIn:23.1-23.35 Error: operator and operand don't agree [tycon mismatch]
  operator domain: ('Z * 'Z list -> bool) * 'Z list
  operand:         [< ty] * [< ty] -> bool
  in expression:
    merge_sort <
-

Я не совсем знаю, что Я делаю не так

Ответы [ 2 ]

1 голос
/ 28 февраля 2020

Использование соглашения о списках имен с множественным «s» и использование одного и того же базового имени для головы и хвоста в шаблонах немедленно устраняет проблему: 

merge (f, x::xs, y::ys) =
        if f(x, xs) then x :: merge (f, xs, y::ys)
                    else y :: merge (f, x::xs, ys);

, где f(x, xs) должен из Конечно, будет f(x, y).

Это соглашение является традиционным, потому что это полезно. Не выходи из дома без него.

0 голосов
/ 27 февраля 2020

У вас есть опечатка; это: 

            if f(a, b) then a :: merge (f, b, x::y)
                       else x :: merge (f, a::b, y);

должно быть так: 

            if f (a, x) then a :: merge (f, b, x::y)
                        else x :: merge (f, a::b, y)

(вызов f на (a, x), а не на (a, b)).

С b и x имеют разные типы ('Z list и 'Z, соответственно), следствием этой опечатки является то, что f подразумевает неправильный тип ('Z * 'Z list -> bool, а не 'Z * 'Z -> bool), поэтому вся функция merge_sort выведена из-за неправильной схемы типов (('a * 'a list -> bool) * 'a list -> 'a list вместо ('a * 'a -> bool) * 'a list -> 'a list).

Некоторые явные аннотации типов (например, запись f : 'a * 'a -> bool в одном месте) могут облегчить компилятор, чтобы помочь вам увидеть, где вы отклоняетесь от типов, которые вы намеревались; но, по общему признанию, если вы еще не знаете, где вы отклоняетесь, то может быть трудно определить, куда добавлять аннотации, чтобы компилятор мог помочь вам найти, где вы отклоняетесь.

...