Главная » Haskell » Рекурсия и корекурсия

0

В языке Haskell нет таких операторов, как for, while или goto. Это связано с тем, что эти операторы явно императивны, то есть они  определяют пошаговый порядок исполнения некоторых инструкций.  Как  уже  было неоднократно упомянуто, язык Haskell, как чистый функциональный язык, не имеет (и не должен иметь) подобных средств. Для организации цикла здесь используется другой механизм — рекурсия.  А такая конструкция, как безусловный переход, просто невыразима в терминах функционального программирования.

Общие понятия

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

В функциональном программировании рекурсия является широко используемым механизмом. Однако в силу декларативности  функционального подхода разработчик программного обеспечения  не  думает о рекурсии как о вызовах функции (что являлось бы определением порядка исполнения программы, то есть отвечало бы на вопрос «как?»). Рекурсия — это средство, с помощью которого

функция может быть определена через себя, то есть использует саму себя в качестве элемента своего определения. Это полностью  аналогично рекурсивным определениям в обычной речи или  математике. Например, в качестве  определения понятия «предок» можно использовать  следующее: «Предок некоего человека — это  его родитель или предок его родителя». Этот пример полностью декларативен, он сжато и ясно объясняет, кто такой предок. По всей видимости, рекурсивные механизмы являются более близкими психологии человека, чем инструкции, в которых объясняются пошаговые алгоритмы.

В качестве примера рекурсивной функции можно рассмотреть тривиальный поиск факториала заданного числа. Эту функцию можно определить следующим образом:

factorial  0  =  1

factorial n = n *  factorial (n  1)

В определении функции для вычисления факториала имеется два момента, которые стоит отметить особо. Во-первых,  это организация цикла. В императивных языках возможно записать вычисление факториала при помощи итерации, определяемой через ключевое слово for. В языке Haskell подобное определение невозможно просто из-за отсутствия подобного ключевого слова и, собственно, идиомы итеративного процесса. Поэтому для организации циклических вычислений используется только рекурсивные функции. Во-вторых, свойства функции factorial могут быть доказаны при помощи математической индукции:

1)                        Факториал для 0 действительно равен единице (по математическому определению).

2)                        Допустим, что доказано, что вызов factorial n возвращает  значение n!.

Необходимо доказать, что вызов factorial (n  + 1) возвратит (n + 1)!.

3)                        Факториал (n + 1) есть произведение  (n + 1) на факториал n  (по определению). Поскольку доказано, что factorial n  возвращает значение n!, вызов factorial (n  + 1),  равный по  определению  функции  произведению (n  + 1) на значение factorial n, вернёт значение (n + 1)! Что и требовалось доказать.

Необходимо обратить внимание на то, что индукция может  использоваться и для создания определений  рекурсивных функций.  В функциональном про-

граммировании это часто используемый приём. Допустим, имеется  необходимость подсчитать произведение всех чисел из некоторого списка. Список является индуктивным типом, определение которого  ограничивается пустым списком. Для пустого списка произведение равно единице. Это естественно, так как n * product  [] должно быть равно n. Произведение же чисел непустого списка будет равно произведению его головы на произведение чисел его хвоста:

product []          = 1

product (x:xs)  = x  *  product  xs

Корекурсия

Теперь можно кратко рассмотреть другой схожий механизм — корекурсию. Корекурсия является дуальным понятием к рекурсии. В  то время как рекурсивные определения работают с данными,  осуществляя «спуск» от начальных значений входных параметров к  таким, на которых происходит остановка рекурсивного процесса, корекурсия работает с коданными, производя «накрутку» значений на начальные величины входных параметров, никогда не останавливаясь.

Понятие коданных  в явном виде не определено в языке  Haskell.  Для  общего понимания имеет смысл привести неформальное определение этого понятия (формально оно определено в рамках теории категорий):

1)                        Коданные, в отличие от данных, скрывают свою структуру.

2)                        В коданных нет атрибутов, имеющих смысл «значение».

3)                        Для коданных существуют только методы доступа. Некоторые из них возвращают данные, некоторые  — коданные.

4)                        Обычно коданные представляют из себя бесконечные  структуры.

В языке Haskell ближайшим отображением коданных могут являться рекурсивные абстрактные типы данных, например список. Ниже корекурсия как раз и будет рассмотрена на примере работы со списками.

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

fibonaccies = 0:1:zipWith (+) fibonaccies (tail  fibonaccies)

Как работает эта функция? Её определение не так тривиально, хотя является классическим при рассмотрении понятия корекурсии в языке Haskell. Для того чтобы понять, как данная функция вычисляет бесконечный список чисел Фибоначчи, можно рассмотреть несколько шагов. Перед этим имеет смысл напомнить, что  функция zipWith из стандартного модуля Prelude  «сшивает» два  списка при помощи заданной операции.

Итак, на вход функции zipWith подаётся операция (+) и два списка: первый — результат вычисления функции fibonacci, второй  — хвост этого результата. Как  быть, если оба списка бесконечны и ещё не вычислены (имеются только первые два элемента: 0 и 1)? Корекурсивная функция вкупе с использованием механизма ленивых вычислений довольствуется малым — использует  то, что есть, то есть первые два элемента списка. Их можно подать на вход функции zipWith, которая применит к ним операцию (+) и получит третий элемент. Далее всё повторяется,  ведь уже имеется три элемента, и можно двигаться далее. Этот процесс можно пояснить следующим рассмотрением вычислений:

fibonaccies:           0  1 1 2 3   5 tail  fibonaccies: 1 1 2  3 5   8 zipWith (+):           1 2 3 5 8 13

Другим хорошим примером, который помогает понять корекурсию, является функция для вычисления бесконечного списка простых чисел, основанная на алгоритме Эратосфена, известном под наименованием «решето Эратосфена»:

primes  =  sieve  [2..] where

sieve   (x:xs) = x:sieve (filter ((/=  0).(‘mod‘ x)) xs)

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

Источник: Душкин Р. В., Справочник по языку Haskell. М.: ДМК Пресс, 2008. 544 с., ил.

По теме:

  • Комментарии