basic Haskell: определение функции сортировки по рекурсии

Question

Так что у меня есть небольшая проблема с функцией сортировки. Мне нужно определить (с помощью рекурсии) функцию я, который принимает в качестве аргумента список аргументов (этот список должен принадлежать Ord), которая выводит упорядоченный список элементов типа . Пример: я [3,2,1] = [1,2,3]

мне удалось прийти с этим решением:

i :: Ord a => [a] -> [a] 

i [] = [] 
i (x:xs) 

| x <= head (xs) = x: i xs 
| otherwise = i xs : x 

Но это не вычислить, выводя много ошибок , Что не так?

Answer 1

Позвольте мне дать вам несколько советов, чтобы вы начали. Прежде всего, давайте исправим форматирование:

i :: Ord a => [a] -> [a] 
i [] = [] 
i (x:xs) 
    | x <= head (xs) = x: i xs 
    | otherwise = i xs : x 

Это выдает ошибку, которая говорит:

In the first argument of ‘(:)’, namely ‘i xs’ 
In the expression: i xs : x 

Теперь это выражение i xs : x проблематично. Тип (:) - (:) :: a -> [a] -> [a]. Но в вашем выражении вы передаете список вместо значения. То, что вы хотели использовать, возможно, было ++. С помощью этого исправляет ошибку компиляции:

i :: Ord a => [a] -> [a] 
i [] = [] 
i (x:xs) 
    | x <= head (xs) = x: i xs 
    | otherwise = i xs ++ [x] 

Теперь, если вы попробуете его в ghci, вы получите исключение во время выполнения:

ghci> i [3,2,1] 
*** Exception: Prelude.head: empty list 

Можете ли вы догадаться, почему? Это потому, что вы не обработали случай, когда список имеет длину 1. Так обработка случай даст вам это:

i :: Ord a => [a] -> [a] 
i [] = [] 
i (x:[]) = [x] 
i (x:xs)    
    | x <= head (xs) = x: i xs 
    | otherwise = i xs ++ [x] 

Теперь, вы можете подумать, что это работает:

ghci> i [3,2,1] 
[1,2,3] 
ghci> i [3,1,2] 
[1,2,3] 

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

ghci> i [2,1,3] 
[1,3,2] 

Надеюсь, этого достаточно, чтобы вы начали.