Изучай 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) равно двум. Если в определении рекурсии у нас есть один или несколько элементов, задаваемых нерекурсивно (F(0) и F(1) в нашем случае), это называется граничными условиями. Граничные условия очень важны, если вы хотите чтобы ваша функция рано или поздно вычислилась. Если бы мы не определили F(0) и F(1) нерекурсивно, мы бы не получили результата, т.к. мы бы достигли нуля и продолжили вычисления с отрицательными числами. В некоторый момент, например, мы бы вычисляли F(-2000) как F(-2001) + F(-2002), и так продолжалось бы бесконечно!

Рекурсия важна для Хаскеля, потому что в отличие от императивных языков, вы выполняете вычисления в Хаскеле, описывая некоторое понятие, а не указывая как его получить. Вот почему в языке нет циклов while и for, вместо этого мы зачастую должны использовать рекурсию, чтобы описать, что собой представляет та или иная сущность.

Максимум прелести

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

Ну а теперь посмотрим, как бы мы сформулировали этот алгоритм рекурсивно. Для начала мы бы определили граничные условия. В пустом списке невозможно найти максимальный элемент. Если список состоит из одного элемента, то максимум равен этому элементу. Затем мы бы сказали, что максимум списка из более чем двух элементов - это первый элемент в списке, если он больше, чем максимальный элемент хвоста. Если максимальный элемент хвоста больше, ну, тогда он и есть максимальный элемент списка. И это всё! Теперь запишем это на Хаскеле.

maximum' :: (Ord a) => [a] -> a

maximum' [] = error "maximum of empty list"

maximum' [x] = x

maximum' (x:xs)

| x > maxTail = x

| otherwise = maxTail

where maxTail = maximum' xs

Как вы видите, сопоставление с образцом отлично дополняет рекурсию! Большинство императивных языков не умеют сопоставлять с образцом, так что потребуется множество операторов if..else для проверки граничных условий. В Хаскеле мы записываем их как шаблоны. Первое граничное условие говорит, что если список пуст - ошибка! В самом деле, какой максимум у пустого списка? Я не знаю. Второй шаблон также описывает граничное условие. Он говорит, что если в списке всего один элемент, его надо вернуть в качестве максимального.

В третьем шаблоне происходит самое интересное. Мы используем сопоставление с образцом для того чтобы разбить список на голову и хвост. Это очень распространенный прием при работе со списками, так что привыкайте. Мы связываем переменную maxTail с максимумом хвоста списка в where. Затем мы проверяем, больше первый элемент списка, чем maxTail, или нет. Если больше, возвращаем его. Иначе мы возвращаем максимум от хвоста списка.

Давайте возьмем конкретный пример и посмотрим, как это все работает: [2,5,1]. Если мы вызовем функцию maximum' с этим значением, первые два шаблона не подойдут. Третий подойдет, список разобьется на 2 и [5,1]. Where хочет знать максимум от [5,1], так что мы заново вызываем функцию с параметром [5,1]. Снова подходит третий шаблон, список разбивается на 5 и [1]. Where хочет знать максимум от [1]. Вызываем функцию для [1]. На сей раз подходит второй шаблон, он возвращает 1. Наконец-то! Возвращаемся на один шаг назад, сравниваем 5 с максимумом от [1] (он равен 1), получаем 5. Теперь мы знаем, что максимум от [5,1] равен 5. Возвращаемся еще на один шаг назад, там где у нас было 2 и [5,1]. Сравнивая 2 и максимум от [5,1], получаем 5.

Еще понятнее эта функция реализуется с использованием max. Если вы помните, max это функция, которая принимает два числа и возвращает большее из них. Вот как мы бы реализовали функцию с использованием max:

maximum' :: (Ord a) => [a] -> a

maximum' [] = error "maximum of empty list"

maximum' [x] = x

maximum' (x:xs) = max x (maximum' xs)

Заценили элегантность? Максимум списка это максимум от первого элемента и максимума от хвоста списка.

Еще немного рекурсивных функций

Теперь, когда мы знаем основы рекурсивного мышления, давайте напишем несколько функций, применяя рекурсию. Для начала реализуем функцию replicate. replicate берет целое число (Int) и некоторый элемент, и возвращает список, который содержит несколько повторений того же элемента. Например, replicate 3 5 вернет [5,5,5]. Давайте обдумаем граничные условия. Думаю, что граничным условием может быть число повторений равное нулю и менее. Если мы попытаемся скопировать что-либо ноль раз, функция должна вернуть пустой список. Так же и для отрицательных чисел, для них функция не имеет смысла.

replicate' :: (Num i, Ord i) => i -> a -> [a]

replicate' n x

| n <= 0 = []

| otherwise = x:replicate' (n-1) x

Мы использовали сторожевые условия вместо шаблонов, потому что мы проверяем булево выражение. Если n меньше либо равно нулю, возвращаем пустой список. В ином случае вернем список, в котором x - первый элемент, затем x повторяется n-1 раз в хвосте. Рано или поздно часть (n-1) приведет к срабатыванию граничного условия.

Замечание: Num не является подклассом Ord. Это означает, что то, что относится к числам, не обязательно должно обладать свойствами отношения порядка. Вот почему мы должны указывать оба класса в ограничениях, когда выполняем сложение, вычитание или сравнение.

Далее, мы реализуем 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 элемент из хвоста. Попытайтесь нарисовать на листе бумаги как будет происходить вычисление, если мы попытаемся взять первые три элемента от списка [4,3,2,1].

Функция reverse обращает список, выстраивая элементы в обратном порядке. Думаем о граничных условиях. Что бы придумать? Это... пустой список, конечно же! Если обратить пустой список, получим тот же пустой список. Так, так. Что на счет всего остального? Ну, можно сказать, что если разбить список на голову и хвост, то обращенный список - это обращенный хвост плюс голова списка в конце.

reverse' :: [a] -> [a]

reverse' [] = []

reverse' (x:xs) = reverse' xs ++ [x]

Готово!

Так как Хаскель умеет работать с бесконечными списками, на самом деле рекурсия не обязательно должна иметь граничные условия. Но если граничных условий нет, рекурсия будет молотить бесконечно или будет производить бесконечную структуру данных, вроде бесконечного списка. Хорошая новость по поводу бесконечных списков - мы можем обрезать их там где нам надо. Функция 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.

Функция 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

Первые два шаблона возвращают пустой список, если первый или второй список пуст. Третий шаблон говорит, что два склеенных списка получаются созданием пары из их голов и повторением процесса для хвостов. Склеивание [1,2,3] и ['a','b'] через два шага будет склеивать [3] и []. Сработает граничное условие, и результатом будет (1,'a'):(2,'b'):[], что в точности то же самое, что и [(1,'a'),(2,'b')].

Давайте реализуем еще одну функцию из стандартной библиотеки - 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 строк, на Хаскеле он много короче и элегантнее. Настолько, что быстрая сортировка на Хаскеле стала притчей во языцех. Только ленивый не приводил пример quicksort для демонстрации элегантности языка. Поэтому давайте напишем ее, несмотря на то что подобный пример считается дурным тоном.

Так, сигнатура функции будет такой:
quicksort :: (Ord a) => [a] -> [a].
Ничего удивительного тут нет. Граничное условие? Пустой список, как и следовало ожидать. Отсортированный пустой список - это пустой список. Затем следует основной алгоритм: отсортированный список – это список, в котором все элементы, меньшие (либо равные) голове списка, идут впереди (в отсортированном порядке), посередине следует голова списка, а потом - все элементы, большие головы списка (также отсортированные). Заметьте, в определении мы упомянули сортировку дважды, так что нам, возможно, придется делать два рекурсивных вызова в теле функции. А также обратите внимание, что мы описали алгоритм просто дав определение отсортированному списку, мы не указывали явно - делай это, затем - делай то... В этом красота функционального программирования! Как нам отфильтровать список, чтобы получить только те элементы списка, которые больше головы списка и – меньшие головы списка? С помощью конструкторов списков (list comprehension). Эх, навались, напишем-ка эту функцию.

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 "the quick brown fox jumps over the lazy dog"

" abcdeeefghhijklmnoooopqrrsttuuvwxyz"

Вах! Это то чего я хотел! Если у нас, скажем, есть список [5, 1, 9, 4, 6, 7, 3], и мы хотим отсортировать его, этот алгоритм сначала возьмет голову, которая равна 5, и затем поместит её в середину двух списков, в которых хранятся элементы меньшие и большие головы списка. То есть, в данный момент у нас будет [1, 4, 3] ++ [5] ++ [9, 6, 7]. Мы знаем, что когда список будет отсортирован, число 5 будет находится на четвёртой позиции, потому что есть три числа меньших чем 5, и три числа больших. Теперь, если мы отсортируем списки [1, 4, 3] и [9, 6, 7], мы получим отсортированный список! Мы сортируем эти два списка той же самой функцией. Рано или поздно мы достигнем пустого списка, который уже отсортирован в силу своей пустоты. Проиллюстрируем:

Элемент, который расположен на своем месте, и больше не будет перемещаться, представлен оранжевым цветом. Если вы просмотрите элементы слева направо, то обнаружите что они отсортированы. Хотя мы решили сравнивать все элементы с "головами", мы можем использовать и другие элементы для сравнения. В алгоритме быстрой сортировки элемент, с которым производится сравнение, называется опорным. Они изображены зеленым цветом. Мы выбрали головной элемент в качестве опорного, потому что его легко получить при сопоставлении с образцом. Элементы, которые меньше опорного - светло-зеленого цвета; элементы, которые больше - тёмно-зеленого. Желтоватый градиент демонстрирует применение быстрой сортировки.

Думая рекурсивно

Мы уже много раз использовали рекурсию, так что, как вы возможно заметили, тут есть определенный шаблон. Обычно вы определяете граничные случаи, а затем задаете функцию, которая что-то делает с некоторыми элементами, и функцию, применяемую для оставшихся элементов. Неважно, список это, дерево, либо другая структура данных. Сумма - это первый элемент списка плюс сумма оставшейся части списка. Произведение списка - это первый элемент списка, умноженный на произведение оставшейся части списка. Длина списка - это единица плюс длина хвоста списка. И так далее, и тому подобное...

Само собой, у всех упомянутых функций есть граничные случаи. Обычно они представляют собой некоторые сценарии выполнения, при которых применение рекурсивного вызова не имеет смысла. Когда имеешь дело со списками, обычно это пустой список. Когда имеешь дело с деревьями, как правило это узел не имеющий потомков.

Похожим образом дело обстоит, если вы рекурсивно обрабатываете числа. Обычно мы работаем с неким числом и функция применяется к тому же числу, но модифицированному некоторым образом. Ранее мы написали функцию для вычисления факториала - он равен произведению числа и факториала от того же числа, уменьшенного на единицу. Такой рекурсивный вызов не имеет смысла для нуля, потому что факториал не определён для отрицательных чисел. Часто граничным значением становится нейтральный элемент. Нейтральный элемент для умножения - 1, так как умножая что-то на 1, вы получаете это самое что-то. Таким же образом при суммировании списка мы полагаем, что сумма пустого списка равна нулю, ноль - нейтральный элемент для сложения. В быстрой сортировке граничный случай это пустой список, он же является нейтральным элементом, так как если присоединить пустой список к некоторому списку, мы снова получим исходный список.

Итак, пытаясь мыслить рекурсивным образом при решении задачи, попробуйте придумать, когда рекурсивное решение не подходит, и понять, можно ли использовать этот вариант как граничный случай. Подумайте, что является нейтральным элементом, как вы будете разбивать параметры функции (например, списки обычно разбивают на голову и хвост путём сопоставления с образцом) и для которой части вы примените рекурсивный вызов.