Главная » Haskell » Накапливающий  параметр и хвостовая рекурсия

0

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

length ::  [a]  ->  Int length [] =  0

length (x:xs)  = 1 + length  xs

Если,  к примеру, рассмотреть вычисления этой  функции  с  аргументом [’a’, ’b’, ’c’], то можно будет увидеть следующую последовательность (здесь символом (==>) обозначается очередной шаг вычислений):

length [’a’,  ’b’, ’c’]

==> 1 + length [’b’, ’c’]

==> 1 + (1  + length [’c’])

==> 1 + (1  + (1  + length []))

==> 1 + (1  + (1  + 0))

==> 1 + (1  + 1)

==> 1 + 2

==> 3

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

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

length_a  ::  [a] ->  Int length_a l  = lngt l 0

lngt :: [a]  ->  Int ->  Int lngt [] n          =  n

lngt (x:xs) n = lngt xs  (n  + 1)

В этом примере второй параметр функции lngt выполняет роль аккумулирующего параметра, именно в нём содержится результат, который возвращается после окончания рекурсии. Сама же рекурсия в этом случае принимает вид

«хвостовой», память при этом расходуется только на хранение адресов возврата функции.

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

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

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

1)                        Вводится новая функция с дополнительным аргументом (аккумулятором), в котором накапливаются результаты вычислений.

2)                        Начальное значение аккумулирующего  параметра задаётся в  равенстве, связывающем старую и новую функции.

3)                        Те равенства исходной функции, которые соответствуют выходу из рекурсии, заменяются возвращением аккумулятора в новой функции.

4)                        Равенства, соответствующие рекурсивному определению, выглядят как обращения к новой функции, в которых аккумулятор получает то значение, которое возвращается исходной функцией.

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

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

По теме:

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