Проблема в сортировке списка SML - PullRequest
Новая
       23

Проблема в сортировке списка SML

0 голосов
/ 30 марта 2019

Я новичок в SML. Я получил этот алгоритм сортировки, чтобы реализовать, где на каждой итерации мне нужно выбрать минимальный элемент из списка, удалить его и создать отсортированный список.

Я сделал кодирование ниже, чтобы решитьпроблема.

Я написал 2 вспомогательные функции, чтобы выбрать минимальный элемент из списка и удалить один элемент из списка. 

fun minList(x::xs) =List.foldl (fn (x,y)=> if x<y then x else y) x (x::xs);

fun remElem(x, l) =
   case l of
   [] => []
 | (x1::x2::xs) => if x1=x then (x2::xs) else (x1::xs)
;

Выше двух программ успешно запущены.

Ниже приведен мой код сортировки. 

fun simpSort(xs)=
let fun aux(xs,acc)=
       case xs of
            [] =>acc
           | [x] => [x]
            | (x::xs) => let val m = minList(xs) 
                       in
                     aux(remElem(m,xs),acc@[m])
                       end
in aux(xs,[])
end;

Эта программа сортировки выдает ошибку.

  • simpSort ([3,1]);

    uncaughtИсключение Совпадение [ошибка неисчерпывающего сопоставления] возбуждено по адресу: стандартный ввод: 433,59

Пожалуйста, сообщите.

1 Ответ

1 голос
/ 01 апреля 2019

Поскольку вы решили свою проблему, вот несколько советов по улучшению рабочей версии вашего кода:

  • Найдите минимум списка способом, который поддерживает пустые списки:

    fun minimum [] = NONE
  | minimum (x::xs) = SOME (foldl Int.min x xs)

  • Упрощение сопоставления с образцом в функции, которая удаляет первое вхождение элемента из списка: 

    fun remove (_, []) = []
  | remove (y, x::xs) =
    if x = y
    then xs
    else x :: remove (y, xs)

  • Используйте этив комбинации написать simpSort: 

    fun simpSort xs =
    case minimum xs of
         NONE => []
       | SOME x => x :: simpSort (remove (x, xs))

Я не должен был говорить, что этот алгоритм сортировки ужасно неэффективен.: -Р

...