Сортировка списков в списке по длине с помощью пузырьковой сортировки - Haskell
У меня есть ввод типа [[a]], и я пытаюсь отсортировать списки в списке по их длине. Я работаю над собственной реализацией пузырьковой сортировки, которая в настоящее время выглядит так:
myInput :: Ord a => [[a]] -> [[a]]
myInput [[]] = [[]]
myInput [[x]] = [[x]]
myInput (x : xs) = mySort x (myInput xs)
mySort :: Ord a => [a] -> [[a]] -> [[a]]
mySort x [[]] = [x]
mySort x (y:ys) | (length x) < (length y) = x:y:ys
| otherwise = y:(myInput x ys)
Однако, когда я ввожу myInput[[1,2],[1]], я получаю неполную ошибку шаблона:
[[1]*** Exception: CourseworkRev.hs:(197,1)-(200,49): Non-exhaustive patterns in function myInput
Я, вероятно, делаю что-то неправильно при объявлении пустых списков, так как это ошибка рекурсии (поправьте меня, если я ошибаюсь). Любые советы о том, как заставить это работать? Спасибо!
Большое спасибо за ваш совет! Я исправляю это просто myInput [] = [[]] ? Я добавил это в свой код, но все равно получаю ту же самую исчерпывающую ошибку шаблона.
нет myInput [] = [] и myInput [x] = [x]..
Что такое myInsert? Если вы сортируете исключительно по длине, то ограничение Ord a является излишним. Вы должны включить -Wall, чтобы компилятор выдал вам подробные предупреждения о том, какие шаблоны вы пропустили (наряду с другими полезными предупреждениями). Если вам нужны только предупреждения шаблона, используйте -Wincomplete-patterns -Wincomplete-uni-patterns.
@dfeuer, да, спасибо, что напомнили мне, что Ord был там, потому что я также использовал ту же функцию в предыдущем назначении для сортировки элементов в списке, поэтому, что касается этого -Wall, я просто ввожу свою функцию с этим флагом? Например myInput[[1,2],[1]] -Wall? Спасибо!
-Wall — это аргумент командной строки для ghc или ghci. Кроме того, вы можете поместить {-# OPTIONS_GHC -Wall #-} в самом верху вашего файла .hs. Или, если вы используете файл Cabal, дайте мне знать, и я напомню себе, как его туда вставить.
Кроме того, в GHCi вы можете в любое время ввести :set -Wall, но это будет выдавать предупреждения только для кода, введенного/загруженного после того, как вы его введете.
Подход с использованием файла Cabal обычно лучше всего подходит для проекта Cabal. В противном случае подход OPTIONS_GHC обычно лучше.
Ответы 1
myInput не имеет шаблона для пустого списка, только для списка с одним элементом, который является пустым списком. Вам, скорее всего, не нужны такие шаблоны, как [[]] и [[x]], так как для списка с одним элементом вы вернете список с этим элементом, независимо от его длины, поэтому:
myInput :: Ord a => [[a]] -> [[a]]
myInput [] = []
myInput [x] = [x]
myInput (x : xs) = mySort x (myInput xs)[[x]] соответствует списку, который содержит только один подсписок [x], который является списком с одним элементом. Так что это будет соответствовать [[1]], но не [[1,2]]. [x], с другой стороны, соответствует любому одноэлементному списку: список с одним элементом, поэтому [[1]], [[1,4]], [[1,4,2,5]] и [[]] будут совпадать.
Большое спасибо, мне тоже нужно было поменять mySort x [[]] = [x] на mySort x [] = [x] и теперь все работает отлично. Теперь я вижу, что я сделал неправильно, действительно запутался с двойными скобками. Большое спасибо!
myInputне имеет шаблона для пустого списка, только для списка с одним элементом, который является пустым списком.