Проблема с сортировкой списка SML
Я новичок в 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;
Эта программа сортировки выдает ошибку.
простая сортировка ([3,1]);
неперехваченное исключение Совпадение [сбой неполного совпадения] поднято по адресу: stdIn:433.59
Пожалуйста, порекомендуйте.
Кроме того, remElem удаляет либо первый, либо второй элемент списка, и ничего больше. Это, вероятно, не то, что вы имели в виду.
Спасибо. Когда я делаю этот код - весело remElem (i, xs) = case xs of []=>[] | x::xs => если i = x, то remElem(i,xs) else x::remElem(i,xs) Он удаляет все вхождения входного символа, где я хочу удалить только первое вхождение.
Я недостаточно ясно выразился; вы удаляете первый элемент, если это первое вхождение, в противном случае вы удаляете второй элемент — независимо от того, что это за второй элемент. Например, remElem(97, [1,2,97]) произведет [1,97], и remElem(12, [1,2,97]) тоже.
Спасибо. Я изменил программу remElem. Теперь это весело remElem(x, l) = case l of [] => [] | [х] => [] | (x1::xs) => если x1=x, то (xs) else x1::remElem(x,xs) ; Это дает правильный результат. Но функция сортировки SimpSort по-прежнему дает ошибочный результат.
Мне удалось это исправить. Я заметил, что неправильно передаю аргументы во вспомогательные функции. Спасибо за помощь.
Ответы 1
Поскольку вы решили свою проблему, вот несколько советов по улучшению рабочей версии вашего кода:
Найдите минимум списка способом, который поддерживает пустые списки:
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))
Я не должен говорить, что этот алгоритм сортировки ужасно неэффективен. :-П
remElemобрабатывает только пустой список и списки, содержащие не менее двух элементов.