Рекурсия

Чтобы понять рекурсию, нужно сначала понять рекурсию.

Эта старая шутка про рекурсию иногда пугает новичков, как в своё время напугала и меня. В действительности в рекурсии нет ничего страшного, и в этой главе мы познакомимся с этим важным механизмом.

Цикл

Удивительно, но в Haskell нет встроенных циклических конструкций, столь привычных для других языков. Ни тебе for, ни тебе while. Однако обойтись без циклов в нашем коде мы не сможем. Как же нам их организовывать?

К счастью, чаще всего нам это и не нужно. Вспомним нашу знакомую, функцию map:

map toUpper someList

Ну и чем же не цикл? На том же C это выглядело бы как-то так:

int length = ...
for(int i = 0; i < length; ++i) {
  char result = toUpper(someList[i]);
  ...
}

Функции наподобие map в подавляющем большинстве случаев избавляют нас от написания явных циклических конструкций, и это не может не радовать. Однако изредка нам всё-так придётся писать циклы явно. В Haskell, из-за отсутствия for-конструкции, сделать это можно только одним способом — через рекурсию (англ. recursion).

Идея рекурсии предельно проста:

Если нам нужно повторить вычисление, производимое некой функцией, мы должны применить эту функцию внутри себя самой. И получится зацикливание.

Взглянем на определение функции map:

map _ []     = []
map f (x:xs) = f x : map f xs

А теперь разберём это интереснейшее определение по косточкам.

Правда о списке

Первым аргументом, как мы помним, выступает некая функция, а вторым — список, к элементам которого применяется эта функция. Но что это за странного вида конструкция в круглых скобках?

(x:xs)

Это — особый образец, используемый для работы со списками. И чтобы он стал понятен, я должен рассказать вам правду о формировании списка.

Как мы помним, формируется список предельно просто:

[1, 2, 3]  -- Список из трёх целых чисел.

Однако в действительности он формируется несколько иначе. Привычная нам конструкция в квадратных скобках есть ни что иное, как синтаксический сахар (англ. syntactic sugar). Синтаксическим сахаром называют некое упрощение кода, делающее его слаще, приятнее для нас. Если же мы уберём сахар (или, как ещё говорят, рассахарим код), то увидим вот что:

1 : 2 : 3 : []

Именно так список из трёх целых чисел формируется на самом деле. Стандартный оператор : нам уже знаком, мы встретились с ним в главе о списках:

newHost   :         hosts

          этот
          оператор

берёт
это
значение
                    и добавляет
                    его в начало
                    этого списка

То есть список строится путём добавления элемента в его «голову», начиная с пустого списка:

  1 : 2 : 3 : []

= 1 : 2 : [3]

= 1 : [2, 3]

= [1, 2, 3]

Начиная с правого края, мы сначала применяем оператор : к 3 и пустому списку, в результате чего получаем список с единственным элементом [3]. Затем, применяя второй оператор : к 2 и к только что полученному списку [3], мы получаем новый список [2, 3]. И в конце, вновь применив оператор : к 1 и к списку [2, 3], мы получаем итоговый список [1, 2, 3]. Вот почему столь удобно оперировать «головой» и «хвостом» списка. И именно поэтому был создан особый образец для паттерн-матчинговой работы со списком:

(head : tail)

В данном случае слова head и tail не относятся к стандартным функциям, я лишь показываю назначение элементов данного образца. Вот более живой пример:

main :: IO ()
main = print first
  where
    (first:others) = ["He", "Li", "Be"]

     _____            ____

           ======           ==========

Поскольку мы точно знаем, что справа у нас список, слева мы пишем образец для списка, в котором first ассоциирован с первым элементом, с «головой», а шаблон others — с оставшимися элементами, с «хвостом».

Но вы спросите, зачем нам это нужно? Если уж мы так хотим работать со списком через паттерн матчинг, можно ведь воспользоваться явным образцом:

main :: IO ()
main = print first
  where
    [first, second, third] = ["He", "Li", "Be"]

     _____                    ____

            ======                  ====

                    +++++                 ++++

Всё верно, однако образец с круглыми скобками чрезвычайно удобен именно для рекурсивной работы со списком, и вот почему. Вспомним определение функции map:

map f (x:xs) = f x : map f xs

       _         _

         ==                ==

Подставим реальные значения на основе примера про перевод символов строки в верхний регистр:

map f       (x:xs) = f       x   : map f       xs

map toUpper "neon" = toUpper 'n' : map toUpper "eon"

             _                _

              ===                               ===

Вот теперь-то мы видим, каким образом функция map пробегается по всему списку. Пройдёмся по итерациям, чтобы всё окончательно встало на свои места. У нас же цикл, верно? А где цикл — там итерации.

На первой из них оператор : применяется к выражениям toUpper 'n' и map toUpper "eon". Выражение слева вычисляется и даёт нам символ 'N':

toUpper 'n' : map toUpper "eon"

'N'         : map toUpper "eon"

Выражение справа содержит применение той же функции map, то есть мы входим в цикл, во вторую его итерацию:

map toUpper "eon" = toUpper 'e' : map toUpper "on"

Выражение слева вычисляется и даёт нам 'E':

toUpper 'e' : map toUpper "on"

'E'         : map toUpper "on"

Вычисляем выражение справа — и входим в следующую итерацию:

map toUpper "on" = toUpper 'o' : map toUpper "n"

Выражение слева даёт нам 'O':

toUpper 'o' : map toUpper "n"

'O'         : map toUpper "n"

Справа вновь применение map — и наша последняя итерация:

map toUpper "n" = toUpper 'n' : map toUpper []

Выражение слева даёт нам 'N':

toUpper 'n' : map toUpper []

'N'         : map toUpper []

Мы вытащили из списка последний из четырёх символов, и список остался пустым. Что же мы будем делать дальше? А дальше мы вспоминаем первый вариант определения функции map:

map _ [] = []

Здесь функция говорит: «Как только я вторым аргументом получу пустой список, я, игнорируя первый аргумент, немедленно дам тот же самый пустой список». Поэтому оставшееся на последней итерации выражение справа:

map toUpper []

подойдёт под данный случай и просто даст нам пустой список. Всё, готово, работа функции завершена. На каждой итерации мы откусываем «голову» списка и передаём её функции toUpper, «хвост» же передаём вновь функции map. На четвёртой итерации упираемся в пустой список и возвращаем его же. Совместив все итерации воедино, получаем вот что:

'N' : 'E' : 'O' : 'N' : []

Узнаёте? Это же наш рассахаренный список, соединяющийся воедино:

['N', 'E', 'O', 'N']

Вот мы и пришли к нашему равенству:

  map toUpper "neon"

= map toUpper ['n', 'e', 'o', 'n']

= ['N', 'E', 'O', 'N']

= "NEON"

Туда и обратно

Определяя рекурсивную функцию, важно помнить о том, что в ней должно быть как правило зацикливания, так и правило выхода из цикла:

map _ []     = []              -- Выходим из цикла.
map f (x:xs) = f x : map f xs  -- Зацикливаемся,
                               -- применяя саму себя.

Если бы мы опустили первое определение, компилятор предусмотрительно сообщил бы нам о проблеме:

Pattern match(es) are non-exhaustive

И это совершенно правильно: если на каждой итерации мы уменьшаем список, то рано или поздно список точно останется пустым, а следовательно, мы обязаны объяснить, что же делать в этом случае.

Для любопытных

Открою секрет: рекурсивными в Haskell бывают не только функции, но и типы. Но об этом в последующих главах.