Миран Липовача - Изучай 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берёт целое число (типа 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 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' :: [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.