Изучай Haskell во имя добра!

Давайте возьмём конкретный пример и посмотрим, как всё это работает. Итак, у нас есть список [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