Изучай Haskell во имя добра! - Миран Липовача

maximum' :: (Ord a) => [a] –> a

maximum' [] = error "максимум в пустом списке"

maximum' [x] = x

maximum' (x:xs) = max x (maximum' xs)

Как вы видите, сопоставление с образцом отлично дополняет рекурсию! Возможность сопоставлять с образцом и разбивать сопоставляемое значение на компоненты облегчает запись подзадач в задаче поиска максимального элемента. Первый образец говорит, что если список пуст – это ошибка! В самом деле, какой максимум у пустого списка? Я не знаю. Второй образец также описывает базовый случай. Он говорит, что если в списке всего один элемент, надо его вернуть в качестве максимального.

В третьем образце происходит самое интересное. Мы используем сопоставление с образцом для того, чтобы разбить список на «голову» и «хвост». Это очень распространённый приём при работе со списками, так что привыкайте. Затем мы вызываем уже знакомую функцию max, которая принимает два параметра и возвращает больший из них. Если x больше наибольшего элемента xs, то вернётся x; в противном случае вернётся наибольший элемент xs. Но как функция maximum' найдёт наибольший элемент xs? Очень просто — вызвав себя рекурсивно.

Давайте возьмём конкретный пример и посмотрим, как всё это работает. Итак, у нас есть список [2,5,1]. Если мы вызовем функцию maximum' с этим значением, первые два образца не подойдут. Третий подойдёт – список разобьётся на 2 и [5,1]. Теперь мы заново вызываем функцию с параметром [5,1]. Снова подходит третий образец, список разбивается на 5 и [1]. Вызываем функцию для [1]. На сей раз подходит второй образец – возвращается 1. Наконец-то! Отходим на один шаг назад, вычисляем максимум 5 и наибольшего элемента [1] (он равен 1), получаем 5. Теперь мы знаем, что максимум [5,1] равен 5. Отступаем ещё на один шаг назад – там, где у нас было 2 и [5,1]. Находим максимум 2 и 5, получаем 5. Таким образом, наибольший элемент [2,5,1] равен 5.

Ещё немного рекурсивных функций

Теперь, когда мы знаем основы рекурсивного мышления, давайте напишем несколько функций, применяя рекурсию. Как и maximum, эти функции в Haskell уже есть, но мы собираемся создать свои собственные версии, чтобы, так сказать, прокачать рекурсивные группы мышц.

Функция replicate

Для начала реализуем функцию replicate. Функция replicate берёт целое число (типа Int) и некоторый элемент и возвращает список, который содержит несколько повторений заданного элемента. Например, replicate 3 5 вернёт список [5,5,5]. Давайте обдумаем базовые случаи. Сразу ясно, что возвращать, если число повторений равно нулю или вообще отрицательное — пустой список. Для отрицательных чисел функция вовсе не имеет смысла.

В общем случае список, состоящий из n повторений элемента x, – это список, имеющий «голову» x и «хвост», состоящий из (n-1)-кратного повторения x. Получаем следующий код:

replicate' :: Int –> a –> [a]

replicate' n x

  | n <= 0 = []

  | otherwise = x : replicate' (n–1) x

Мы использовали сторожевые условия вместо образцов потому, что мы проверяем булевы выражения.

Функция take

Теперь реализуем функцию take. Эта функция берёт определённое количество первых элементов из заданного списка. Например, take 3 [5,4,3,2,1] вернёт список [5,4,3]. Если мы попытаемся получить ноль или менее элементов из списка, результатом будет пустой список. Если попытаться получить какую-либо часть пустого списка, функция тоже возвратит пустой список. Заметили два базовых случая? Ну, давайте это запишем:

take' :: (Num i, Ord i) => i –> [a] –> [a]

take' n _

  | n <= 0     = []

take' _ []     = []

take' n (x:xs) = x : take' (n–1) xs

Заметьте, что в первом образце, который соответствует случаю, когда мы хотим взять нуль или меньше элементов, мы используем маску. Маска _ используется для сопоставления со списком, потому что сам список нас в данном случае не интересует. Также обратите внимание, что мы применяем охранное выражение, но без части otherwise. Это означает, что если значение n будет больше нуля, сравнение продолжится со следующего образца. Второй образец обрабатывает случай, когда мы пытаемся получить часть пустого списка, – возвращается пустой список. Третий образец разбивает список на «голову» и «хвост». Затем мы объявляем, что получить n элементов от списка – это то же самое, что взять «голову» списка и добавить (n–1) элемент из «хвоста».

Функция 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, чтобы наглядно продемонстрировать изящество языка. Давайте и мы напишем её, несмотря на то что подобный пример уже считается дурным тоном.