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)
элемент из «хвоста».