>reverse' :: [a] –> [a]

>reverse' [] = []

>reverse' (x:xs) = reverse' xs ++ [x]

Готово!

Функция >repeat принимает на вход некоторый элемент и возвращает бесконечный список, содержащий этот элемент. Рекурсивное определение такой функции довольно просто – судите сами:

>repeat' :: a –> [a]

>repeat' x = x:repeat' x

Вызов >repeat 3 даст нам список, который начинается с тройки и содержит бесконечное количество троек в хвостовой части. Вызов будет вычислен как >3:repeat 3, затем как >3:(3:repeat 3), >3:(3:(3: repeat 3)) и т. д. Вычисление >repeat 3 не закончится никогда, а вот >take 5 (repeat 3) выдаст нам список из пяти троек. Это то же самое, что вызвать >replicate 5 3.

Функция >repeat наглядно показывает, что рекурсия может вообще не иметь базового случая, если она создаёт бесконечные списки – нам нужно только вовремя их где-нибудь обрезать.

Функция >zip берёт два списка и стыкует их, образуя список пар (по аналогии с тем, как застёгивается замок-молния). Так, например, >zip [1,2,3] ['a','b'] вернёт список >[(1,'a'),(2,'b')]. При этом более длинный список, как видите, обрезается до длины короткого. Ну а если мы состыкуем что-либо с пустым списком? Получим пустой список! Это базовый случай. Но так как функция принимает на вход два списка, то на самом деле это два базовых случая.

>zip' :: [a] –> [b] –> [(a,b)]

>zip' _ [] = []

>zip' [] _ = []

>zip' (x:xs) (y:ys) = (x,y):zip' xs ys

Первые два образца соответствуют базовым случаям: если первый или второй список пустые, возвращается пустой список. В третьем образце говорится, что склеивание двух списков эквивалентно созданию пары из их «голов» и присоединению этой пары к результату склеивания «хвостов».

Например, если мы вызовем >zip' со списками >[1,2,3] и >['a','b'], то первым элементом результирующего списка станет пара >(1,>'a'), и останется склеить списки >[2,3] и >['b']. После ещё одного рекурсивного вызова функция попытается склеить >[3] и >[], что будет сопоставлено с первым образцом. Окончательным результатом теперь будет список >(1,'a'):((2,'b'):[]), то есть, по сути, >[(1,'a'),(2,'b')].

Давайте реализуем ещё одну функцию из стандартной библиотеки – >elem. Она принимает элемент и список и проверяет, есть ли заданный элемент в этом списке. Как обычно, базовый случай — это пустой список. Мы знаем, что в пустом списке нет элементов, так что в нём определённо нет ничего, что мы могли бы искать.

>elem' :: (Eq a) => a –> [a] –> Bool

>elem' a [] = False

>elem' a (x:xs)

>  | a == x = True

>  | otherwise = a `elem'` xs

Довольно просто и ожидаемо. Если «голова» не является искомым элементом, мы проверяем «хвост». Если мы достигли пустого списка, то результат – >False.

Итак, у нас есть список элементов, которые могут быть отсортированы. Их тип – экземпляр класса >Ord. А теперь требуется их отсортировать! Для этого предусмотрен очень классный алгоритм, называемый быстрой сортировкой (quicksort). Это довольно-таки хитроумный способ. В то время как его реализация на императивных языках занимает многим более 10 строк, на языке Haskell он намного короче и элегантнее. Настолько, что быстрая сортировка на Haskell стала притчей во языцех. Только ленивый не приводил пример определения функции