Привет, рекурсия!
В предыдущей главе мы кратко затронули рекурсию. Теперь мы изучим её более подробно, узнаем, почему она так важна для языка Haskell и как мы можем создавать лаконичные и элегантные решения, думая рекурсивно.
Если вы всё ещё не знаете, что такое рекурсия, прочтите это предложение ещё раз. Шучу!.. На самом деле рекурсия – это способ определять функции таким образом, что функция применяется в собственном определении. Стратегия решения при написании рекурсивно определяемых функций заключается в разбиении задачи на более мелкие подзадачи того же вида и в попытке их решения путём разбиения при необходимости на ещё более мелкие. Рано или поздно мы достигаем базовый случай (или базовые случаи) задачи, разбить который на подзадачи не удаётся и который требует написания явного (нерекурсивного) решения.
Многие понятия в математике даются рекурсивно. Например, последовательность чисел Фибоначчи. Мы определяем первые два числа Фибоначчи не рекурсивно. Допустим, F(0) = 0 и F(1) = 1; это означает, что нулевое и первое число из ряда Фибоначчи – это ноль и единица. Затем мы определим, что для любого натурального числа число Фибоначчи представляет собой сумму двух предыдущих чисел Фибоначчи. Таким образом, F(n) = F(n – 1) + F(n – 2). Получается, что F(3) – это F(2) + F(1), что в свою очередь даёт (F(1) + F(0)) + F(1). Так как мы достигли чисел Фибоначчи, заданных не рекурсивно, то можем точно сказать, что F(3) равно двум.
Рекурсия исключительно важна для языка Haskell, потому что, в отличие от императивных языков, вы выполняете вычисления в Haskell, описывая некоторое понятие, а не указывая, как его получить. Вот почему в этом языке нет циклов типа while и for – вместо этого мы зачастую должны использовать рекурсию, чтобы описать, что представляет собой та или иная сущность.
Максимум удобства
Функция 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.
Ещё немного рекурсивных функций
Теперь, когда мы знаем основы рекурсивного мышления, давайте напишем несколько функций, применяя рекурсию. Как и 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 обращает список, выстраивая элементы в обратном порядке. И снова пустой список оказывается базовым случаем, потому что если обратить пустой список, получим тот же пустой список. Хорошо… А что насчёт всего остального? Ну, можно сказать, что если разбить список на «голову» и «хвост», то обращённый список – это обращённый «хвост» плюс «голова» списка в конце.
reverse' :: [a] –> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
Готово!
Функция repeat
Функция 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.
Функция repeat наглядно показывает, что рекурсия может вообще не иметь базового случая, если она создаёт бесконечные списки – нам нужно только вовремя их где-нибудь обрезать.
Функция zip
Функция zip берёт два списка и стыкует их, образуя список пар (по аналогии с тем, как застёгивается замок-молния). Так, например, zip [1,2,3] ['a','b'] вернёт список [(1,'a'),(2,'b')]. При этом более длинный список, как видите, обрезается до длины короткого. Ну а если мы состыкуем что-либо с пустым списком? Получим пустой список! Это базовый случай. Но так как функция принимает на вход два списка, то на самом деле это два базовых случая.
zip' :: [a] –> [b] –> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys
Первые два образца соответствуют базовым случаям: если первый или второй список пустые, возвращается пустой список. В третьем образце говорится, что склеивание двух списков эквивалентно созданию пары из их «голов» и присоединению этой пары к результату склеивания «хвостов».
Например, если мы вызовем zip' со списками [1,2,3] и ['a','b'], то первым элементом результирующего списка станет пара (1, 'a'), и останется склеить списки [2,3] и ['b']. После ещё одного рекурсивного вызова функция попытается склеить [3] и [], что будет сопоставлено с первым образцом. Окончательным результатом теперь будет список (1,'a'):((2,'b'):[]), то есть, по сути, [(1,'a'),(2,'b')].
Функция elem
Давайте реализуем ещё одну функцию из стандартной библиотеки – elem. Она принимает элемент и список и проверяет, есть ли заданный элемент в этом списке. Как обычно, базовый случай — это пустой список. Мы знаем, что в пустом списке нет элементов, так что в нём определённо нет ничего, что мы могли бы искать.
elem' :: (Eq a) => a –> [a] –> Bool
elem' a [] = False
elem' a (x:xs)
| a == x = True
| otherwise = a `elem'` xs
Довольно просто и ожидаемо. Если «голова» не является искомым элементом, мы проверяем «хвост». Если мы достигли пустого списка, то результат – False.
Сортируем, быстро!..
Итак, у нас есть список элементов, которые могут быть отсортированы. Их тип – экземпляр класса Ord. А теперь требуется их отсортировать! Для этого предусмотрен очень классный алгоритм, называемый быстрой сортировкой (quicksort). Это довольно-таки хитроумный способ. В то время как его реализация на императивных языках занимает многим более 10 строк, на языке Haskell он намного короче и элегантнее. Настолько, что быстрая сортировка на Haskell стала притчей во языцех. Только ленивый не приводил пример определения функции quicksort, чтобы наглядно продемонстрировать изящество языка. Давайте и мы напишем её, несмотря на то что подобный пример уже считается дурным тоном.
Алгоритм
Итак, сигнатура функции будет следующей:
quicksort :: (Ord a) => [a] –> [a]
Ничего удивительного тут нет. Базовый случай? Пустой список, как и следовало ожидать. Отсортированный пустой список – это пустой список. Затем следует основной алгоритм: отсортированный список – это список, в котором все элементы, меньшие либо равные «голове» списка, идут впереди (в отсортированном порядке), посередине следует «голова» списка, а потом – все элементы, большие «головы» списка (также отсортированные). Заметьте, в определении мы упомянули сортировку дважды, так что нам, возможно, придётся делать два рекурсивных вызова в теле функции. Также обратите внимание на то, что мы описали алгоритм, просто дав определение отсортированному списку. Мы не указывали явно: «делай это, затем делай то…» В этом красота функционального программирования! Как нам отфильтровать список, чтобы получить только те элементы, которые больше «головы» списка, и те, которые меньше? С помощью генераторов списков.
Если у нас, скажем, есть список [5,1,9,4,6,7,3] и мы хотим отсортировать его, этот алгоритм сначала возьмёт «голову», которая равна 5, и затем поместит её в середину двух списков, где хранятся элементы меньшие и большие «головы» списка. То есть в нашем примере получается следующее: [1,4,3] ++ [5] ++ [9,6,7]. Мы знаем, что когда список будет отсортирован, число 5 будет находиться на четвёртой позиции, потому что есть три числа меньше и три числа больше 5. Теперь, если мы отсортируем списки [1,4,3] и [9,6,7], то получится отсортированный список! Мы сортируем эти два списка той же самой функцией. Рано или поздно мы достигнем пустого списка, который уже отсортирован – в силу своей пустоты. Проиллюстрируем (цветной вариант рисунка приведён на форзаце книги):
Элемент, который расположен на своём месте и больше не будет перемещаться, выделен оранжевым цветом. Если вы просмотрите элементы слева направо, то обнаружите, что они отсортированы. Хотя мы решили сравнивать все элементы с «головами», можно использовать и другие элементы для сравнения. В алгоритме быстрой сортировки элемент, с которым производится сравнение, называется опорным. На нашей картинке такие отмечены зелёным цветом. Мы выбрали головной элемент в качестве опорного, потому что его легко получить при сопоставлении с образцом. Элементы, которые меньше опорного, обозначены светло-зелёным цветом; элементы, которые больше, – темно-зелёным. Желтоватый градиент демонстрирует применение быстрой сортировки.
Определение
quicksort :: (Ord a) => [a] –> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort [a | a <– xs, a <= x]
biggerSorted = quicksort [a | a <– xs, a > x]
in smallerSorted ++ [x] ++ biggerSorted
Давайте немного «погоняем» функцию – так сказать, испытаем её в действии:
ghci> quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]
[1,2,2,3,3,4,4,5,6,7,8,9,10]
ghci> quicksort "съешь ещё этих мягких французских булок, да выпей чаю"
" ,ааабвгдеееёзииийккклмнопрсстууфхххцчшщъыьэюя"
Ура! Это именно то, чего я хотел!
Думаем рекурсивно
Мы уже много раз использовали рекурсию, и, как вы, возможно, заметили, тут есть определённый шаблон. Обычно вы определяете базовые случаи, а затем задаёте функцию, которая что-либо делает с рядом элементов, и функцию, применяемую к оставшимся элементам. Неважно, список ли это, дерево либо другая структура данных. Сумма – это первый элемент списка плюс сумма оставшейся его части. Произведение списка – это первый его элемент, умноженный на произведение оставшейся части. Длина списка – это единица плюс длина «хвоста» списка. И так далее, и тому подобное…
Само собой разумеется, у всех упомянутых функций есть базовые случаи. Обычно они представляют собой некоторые сценарии выполнения, при которых применение рекурсивного вызова не имеет смысла. Когда имеешь дело со списками, это, как правило, пустой список. Когда имеешь дело с деревьями, это в большинстве случаев узел, не имеющий потомков.
Похожим образом обстоит дело, если вы рекурсивно обрабатываете числа. Обычно мы работаем с неким числом, и функция применяется к тому же числу, но модифицированному некоторым образом. Ранее мы написали функцию для вычисления факториала – он равен произведению числа и факториала от того же числа, уменьшенного на единицу. Такой рекурсивный вызов не имеет смысла для нуля, потому что факториал не определён для отрицательных чисел. Часто базовым значением становится нейтральный элемент. Нейтральный элемент для умножения – 1, так как, умножая нечто на 1, вы получаете это самое нечто. Таким же образом при суммировании списка мы полагаем, что сумма пустого списка равна нулю, нуль – нейтральный элемент для сложения. В быстрой сортировке базовый случай – это пустой список; он же является нейтральным элементом, поскольку если присоединить пустой список к некоторому списку, мы снова получим исходный список.
Итак, пытаясь мыслить рекурсивным образом при решении задачи, попробуйте придумать, в какой ситуации рекурсивное решение не подойдёт, и понять, можно ли использовать этот вариант как базовый случай. Подумайте, что является нейтральным элементом, как вы будете разбивать параметры функции (например, списки обычно разбивают на «голову» и «хвост» путём сопоставления с образцом) и для какой части примените рекурсивный вызов.