Функция reverse
Функция reverse обращает список, выстраивая элементы в обратном порядке. И снова пустой список оказывается базовым случаем, потому что если обратить пустой список, получим тот же пустой список. Хорошо… А что насчёт всего остального? Ну, можно сказать, что если разбить список на «голову» и «хвост», то обращённый список – это обращённый «хвост» плюс «голова» списка в конце.
reverse' :: [a] –> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
Готово!
Функция repeat
Функция 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 берёт два списка и стыкует их, образуя список пар (по аналогии с тем, как застёгивается замок-молния). Так, например, 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. Она принимает элемент и список и проверяет, есть ли заданный элемент в этом списке. Как обычно, базовый случай — это пустой список. Мы знаем, что в пустом списке нет элементов, так что в нём определённо нет ничего, что мы могли бы искать.
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 стала притчей во языцех. Только ленивый не приводил пример определения функции quicksort, чтобы наглядно продемонстрировать изящество языка. Давайте и мы напишем её, несмотря на то что подобный пример уже считается дурным тоном.
Алгоритм
Итак, сигнатура функции будет следующей:
quicksort :: (Ord a) => [a] –> [a]
Ничего удивительного тут нет. Базовый случай? Пустой список, как и следовало ожидать. Отсортированный пустой список – это пустой список. Затем следует основной алгоритм: отсортированный список – это список, в котором все элементы, меньшие либо равные «голове» списка, идут впереди (в отсортированном порядке), посередине следует «голова» списка, а потом – все элементы, большие «головы» списка (также отсортированные). Заметьте, в определении мы упомянули сортировку дважды, так что нам, возможно, придётся делать два рекурсивных вызова в теле функции. Также обратите внимание на то, что мы описали алгоритм, просто дав определение отсортированному списку. Мы не указывали явно: «делай это, затем делай то…» В этом красота функционального программирования! Как нам отфильтровать список, чтобы получить только те элементы, которые больше «головы» списка, и те, которые меньше? С помощью генераторов списков.