Максимум удобства

Функция maximum принимает список упорядочиваемых элементов (то есть экземпляров класса Ord) и возвращает максимальный элемент. Подумайте, как бы вы реализовали эту функцию в императивном стиле. Вероятно, завели бы переменную для хранения текущего значения максимального элемента – и затем в цикле проверяли бы элементы списка. Если элемент больше, чем текущее максимальное значение, вы бы замещали его новым значением. То, что осталось в переменной после завершения цикла, – и есть максимальный элемент. Ух!.. Довольно много слов потребовалось, чтобы описать такой простой алгоритм!

Ну а теперь посмотрим, как можно сформулировать этот алгоритм рекурсивно. Для начала мы бы определили базовые случаи. В пустом списке невозможно найти максимальный элемент. Если список состоит из одного элемента, то максимум равен этому элементу. Затем мы бы сказали, что максимум списка из более чем двух элементов – это большее из двух чисел: первого элемента («головы») или максимального элемента оставшейся части списка («хвоста»). Теперь запишем это на языке 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.