Изучай Haskell во имя добра! (Липовача) - страница 40

Функция >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]. Снова подходит третий образец, список разбивается на