>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 обращает список, выстраивая элементы в обратном порядке. И снова пустой список оказывается базовым случаем, потому что если обратить пустой список, получим тот же пустой список. Хорошо… А что насчёт всего остального? Ну, можно сказать, что если разбить список на «голову» и «хвост», то обращённый список – это обращённый «хвост» плюс «голова» списка в конце.