Корекурсия

Не путать с взаимной рекурсией .

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

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

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

Примеры

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

Факториал

Классическим примером рекурсии является вычисление факториала , который рекурсивно определяется как 0! := 1 и n! := n × (n - 1)! .

Чтобы рекурсивно вычислить результат для заданного ввода, рекурсивная функция вызывает (копию) себя с другим («меньшим» в некотором роде) вводом и использует результат этого вызова для построения своего результата. Рекурсивный вызов делает то же самое, если не базовый случай был достигнут . Таким образом, стек вызовов в процессе развивается . Например, чтобы вычислить fac(3) , это рекурсивно вызывает по очереди fac(2) , fac(1) , fac(0) («завершение» стека), после чего рекурсия завершается с fac(0) = 1. , а затем стек раскручивается в обратном порядке, и результаты вычисляются на обратном пути по стеку вызовов к начальному кадру вызова fac(3), который использует результат fac(2) = 2 для вычисления окончательного результата как 3 × 2 = 3 × fac(2) =: fac(3) и, наконец, верните fac(3) = 6 . В этом примере функция возвращает одно значение.

Это раскручивание стека можно объяснить, определив факториал corecursive как итератор , где каждый начинает со случая $1=:0!$, затем из этого начального значения конструируются значения факториала для увеличения чисел 1, 2, 3... как в приведенном выше рекурсивном определении с перевернутой «стрелкой времени», так сказать, путем чтения ее назад как $n!\times (n+1)=:(n+1)!$. корекурсивный алгоритм создает поток всех Определенный таким образом факториалов. Это может быть конкретно реализовано в виде генератора . Символически, отметив, что для вычисления следующего значения факториала требуется отслеживать как n, так и f (предыдущее значение факториала), это можно представить как:

$n,f=(0,1):(n+1,f\times (n+1))$

или в Хаскеле ,

  (\(n,f) -> (n+1, f*(n+1))) `iterate` (0,1)

то есть «начиная с $n,f=0,1$, на каждом шаге последующие значения рассчитываются как $n+1,f\times (n+1)$". Это математически эквивалентно и почти идентично рекурсивному определению, но $+1$ подчеркивает, что значения факториала строятся вперед от начального случая, а не вычисляются после первого перехода назад, вплоть до базового случая, с помощью $-1$ декремент. Прямой вывод функции corecursive не просто содержит факториал $n!$ значения, но также включает для каждого значения вспомогательные данные его индекса n в последовательность, так что любой конкретный результат может быть выбран среди всех них по мере необходимости.

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

В Python рекурсивную функцию факториала можно определить как:

def factorial(n: int) -> int:
    """Recursive factorial function."""
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Тогда это можно было бы назвать, например, как factorial(5) вычислить 5! .

Соответствующий корекурсивный генератор можно определить как:

def factorials():
    """Corecursive generator."""
    n, f = 0, 1
    while True:
        yield f
        n, f = n + 1, f * (n + 1)

Это генерирует бесконечный поток факториалов по порядку; конечная его часть может быть произведена путем:

def n_factorials(n: int):
    k, f = 0, 1
    while k <= n:
        yield f
        k, f = k + 1, f * (k + 1)

Затем это можно было бы вызвать для получения факториалов до 5! с помощью:

for f in n_factorials(5):
    print(f)

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

def nth_factorial(n: int):
    k, f = 0, 1
    while k < n:
        k, f = k + 1, f * (k + 1)
    return f

Как можно легко увидеть здесь, это практически эквивалентно (просто заменив return для единственного yield там) к технике аргумента аккумулятора для хвостовой рекурсии , развернутой в явный цикл. Таким образом, можно сказать, что концепция корекурсии представляет собой объяснение воплощения итеративных вычислительных процессов посредством рекурсивных определений, где это применимо.

Последовательность Фибоначчи

Таким же образом последовательность Фибоначчи можно представить как:

$a,b=(0,1):(b,a+b)$

Поскольку последовательность Фибоначчи является рекуррентным отношением второго порядка, корекурсивное отношение должно отслеживать два последовательных члена с $(b,-)$ соответствует сдвигу вперед на один шаг, а $(-,a+b)$ соответствующий вычислению следующего члена. Затем это можно реализовать следующим образом (с использованием параллельного присваивания ):

def fibonacci_sequence():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

В Хаскеле

 map fst ( (\(a,b) -> (b,a+b)) `iterate` (0,1) )

Обход дерева

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

Итеративно можно перемещаться по дереву, помещая его корневой узел в структуру данных, затем повторяя эту структуру данных, пока она не пуста, на каждом шаге удаляя из нее первый узел и помещая дочерние узлы удаленного узла обратно в эти данные. структура. Если структура данных представляет собой стек (LIFO), это дает обход в глубину, а если структура данных представляет собой очередь (FIFO), это дает обход в ширину:

${\text{trav}}_{\text{nn}}(t)={\text{aux}}_{\text{nn}}([t])$

${\text{aux}}_{\text{df}}([t,\ ...ts])={\text{val}}(t);\ {\text{aux}}_{\text{df}}([\ ...{\text{children}}(t),\ ...ts\ ])$

${\text{aux}}_{\text{bf}}([t,\ ...ts])={\text{val}}(t);\ {\text{aux}}_{\text{bf}}([\ ...ts,\ ...{\text{children}}(t)\ ])$

Используя рекурсию, обход дерева в глубину реализуется просто как рекурсивный обход каждого из дочерних узлов корневого узла по очереди. Таким образом, второе дочернее поддерево не обрабатывается до тех пор, пока не будет завершено первое дочернее поддерево. Значение корневого узла обрабатывается отдельно: до прохождения первого дочернего узла (что приводит к обходу в предварительном порядке), после завершения первого и перед вторым (по порядку) или после завершения второго дочернего узла (после завершения). порядок) — для простоты изложения предполагается, что дерево двоичное. Стек вызовов (вызовов функций рекурсивного обхода) соответствует стеку, который будет перебираться с помощью явной манипуляции со структурой LIFO, упомянутой выше. Символически,

${\text{df}}_{\text{in}}(t)=[\ ...{\text{df}}_{\text{in}}({\text{left}}(t)),\ {\text{val}}(t),\ ...{\text{df}}_{\text{in}}({\text{right}}(t))\ ]$

${\text{df}}_{\text{pre}}(t)=[\ {\text{val}}(t),\ ...{\text{df}}_{\text{pre}}({\text{left}}(t)),\ ...{\text{df}}_{\text{pre}}({\text{right}}(t))\ ]$

${\text{df}}_{\text{post}}(t)=[\ ...{\text{df}}_{\text{post}}({\text{left}}(t)),\ ...{\text{df}}_{\text{post}}({\text{right}}(t)),\ {\text{val}}(t)\ ]$

«Рекурсия» здесь имеет два значения. Во-первых, рекурсивные вызовы функций обхода дерева ${\text{df}}_{xyz}$. Более уместно то, что нам нужно разобраться с тем, как результирующий список значений здесь строится . Рекурсивное создание выходных данных снизу вверх приведет к обходу дерева справа налево. Чтобы это действительно выполнялось в заданном порядке слева направо, последовательность должна быть обеспечена какими-то внешними средствами, или это было бы достигнуто автоматически, если бы выходные данные были построены сверху вниз, то есть коркурсивно .

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

$v,ts=([],[{\text{FullTree}}]):({\text{RootValues}}(ts),{\text{ChildTrees}}(ts))$

это означает, что на каждом шаге выводится список значений в узлах этого уровня, а затем переходите к узлам следующего уровня. Для создания только значений узлов из этой последовательности просто требуется отбросить вспомогательные данные дочернего дерева, а затем сгладить список списков (значения изначально группируются по уровню (глубине); сглаживание (разгруппировка) дает плоский линейный список). Это экстенсионально эквивалентно ${\text{aux}}_{\text{bf}}$ спецификация выше. В Хаскеле

 concatMap fst ( (\(v, ts) -> (rootValues ts, childTrees ts)) `iterate` ([], [fullTree]) )

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

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

def df(node):
    """Post-order depth-first traversal."""
    if node is not None:
        df(node.left)
        df(node.right)
        print(node.value)

Затем это можно вызвать с помощью df(t) для печати значений узлов дерева в обратном порядке в глубину.

Корекурсивный генератор в ширину можно определить как:

def bf(tree):
    """Breadth-first corecursive generator."""
    tree_list = [tree]
    while tree_list:
        new_tree_list = []
        for tree in tree_list:
            if tree is not None:
                yield tree.value
                new_tree_list.append(tree.left)
                new_tree_list.append(tree.right)
        tree_list = new_tree_list

Затем его можно вызвать для печати значений узлов дерева в порядке ширины:

for i in bf(t):
    print(i)

Определение

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

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

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

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

Обсуждение

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

В «Программирование с потоками в Coq: пример: Решето Эратосфена» мы находим

hd (conc a s) = a               
tl (conc a s) = s

(sieve p s) = if div p (hd s) then sieve p (tl s)
              else conc (hd s) (sieve p (tl s))

hd (primes s) = (hd s)          
tl (primes s) = primes (sieve (hd s) (tl s))

где простые числа «получаются путем применения операции простых чисел к потоку (Enu 2)». Следуя приведенным выше обозначениям, последовательность простых чисел (с префиксом 0) и потоки чисел, постепенно просеиваемые, можно представить как

$p,s=(0,[2..]):(hd(s),sieve(hd(s),tl(s)))$

или в Хаскеле,

(\(p, s@(h:t)) -> (h, sieve h t)) `iterate` (0, [2..])

Авторы обсуждают, как определение sieve не всегда гарантированно будет продуктивным и может застрять, например, если вызвать с помощью [5,10..] в качестве начального потока.

Вот еще один пример на Haskell. Следующее определение создает список чисел Фибоначчи в линейном времени:

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

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

Это также можно сделать на Python:

>>> from itertools import tee, chain, islice
>>> def fibonacci():
...     def deferred_output():
...         yield from output
...
...     result, c1, c2 = tee(deferred_output(), 3)
...     paired = (x + y for x, y in zip(c1, islice(c2, 1, None)))
...     output = chain([0, 1], paired)
...     return result
>>> print(*islice(fibonacci(), 20), sep=', ')
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181

Определение zipWith может быть встроен, что приведет к следующему:

fibs = 0 : 1 : next fibs
  where
    next (a: t@(b:_)) = (a+b):next t

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

fibs = fibgen (0,1)
fibgen (x,y) = x : fibgen (y,x+y)

используется только самореферентная функция При этом для построения результата . Если бы он использовался со строгим конструктором списка, это был бы пример неконтролируемой рекурсии, но с нестрогим конструктором списка эта защищенная рекурсия постепенно создает неопределенно определенный список.

Корекурсия не обязательно должна создавать бесконечный объект; корекурсивная очередь является особенно хорошим примером этого явления. Следующее определение производит обход двоичного дерева в ширину сверху вниз сглаживание за линейное время (уже включая упомянутое выше ):

data Tree a b = Leaf a
              | Branch b (Tree a b) (Tree a b)

bftrav :: Tree a b -> [Tree a b]
bftrav tree = tree : ts
  where
  ts = gen 1 (tree : ts)

  gen  0   p                 =         []           
  gen len (Leaf   _     : p) =         gen (len-1) p
  gen len (Branch _ l r : p) = l : r : gen (len+1) p
  --       ----read----        ----write-ahead---

-- bfvalues tree = [v | (Branch v _ _) <- bftrav tree]

Это определение берет дерево и создает список его поддеревьев (узлов и листьев). Этот список служит двойной цели: как входная очередь, так и результат ( gen len p производит свою продукцию len метки перед входным обратным указателем, p, по списку). Оно конечно тогда и только тогда, когда исходное дерево конечно. Длина очереди должна явно отслеживаться, чтобы обеспечить завершение; это можно смело опустить, если это определение применять только к бесконечным деревьям.

Этот код на Haskell использует самоссылающуюся структуру данных, но по существу не зависит от ленивых вычислений. Его можно напрямую перевести, например, на Пролог, который не является ленивым языком. Что важно , так это возможность построить список (используемый в качестве очереди) нисходящим способом . Для этого в Прологе есть минусы хвостовой рекурсии по модулю (т.е. открытые списки). Это также можно эмулировать в Scheme, C и т. д. с использованием связанных списков с изменяемым хвостовым указателем:

bftrav( Tree,  [Tree|TS]) :- bfgen( 1, [Tree|TS],   TS).

bfgen( 0, _,   []) :- !.  % 0 entries in the queue -- stop and close the list
bfgen( N, [leaf(_)      |P],   TS      ) :- N2 is N-1, bfgen( N2, P,   TS).
bfgen( N, [branch(_,L,R)|P],   [L,R|TS]) :- N2 is N+1, bfgen( N2, P,   TS).
%%         ----read-----      --write-ahead--

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

label :: Tree a b -> Tree Int Int 
label t = tn
  where
  (tn, ns) = go t (1:ns)

  go :: Tree a b -> [Int] ->  (Tree Int Int, [Int])
  go (Leaf   _    ) (i:a) = (Leaf   i      , i+1:a)
  go (Branch _ l r) (i:a) = (Branch i ln rn, i+1:c)
       where
       (ln, b) = go l a
       (rn, c) = go r b

Или в Прологе, для сравнения,

label( Tree, Tn) :- label( Tree, [1|Ns],   Tn, Ns).

label( leaf(_),      [I|A],   leaf(  I),      [I+1|A]).
label( branch(_,L,R),[I|A],   branch(I,Ln,Rn),[I+1|C]) :-
  label( L, A,   Ln, B),  
  label( R, B,   Rn, C).

Апоморфизм катаморфизм (например, анаморфизм , такой как развертка ) является формой корекурсии точно так же, как параморфизм (например, , такой как сгиб ) является формой рекурсии.

Помощник проверки Coq поддерживает корекурсию и коиндукцию с помощью команды CoFixpoint.

История

Корекурсия, называемая циклическим программированием, восходит, по крайней мере, к ( Bird 1984 ), в котором упоминаются Джон Хьюз и Филип Уодлер ; более общие формы были разработаны в ( Allison 1989 ). Первоначальные мотивы включали создание более эффективных алгоритмов (позволяющих в некоторых случаях один проход данных вместо необходимости нескольких проходов) и реализацию классических структур данных, таких как двусвязные списки и очереди, на функциональных языках.

См. также

• Бисимуляция
• Коиндукция
• Рекурсия
• Анаморфизм

Ссылки

• Берд, Ричард Симпсон (1984). «Использование циклических программ для устранения многократного обхода данных». Акта Информатика . 21 (3): 239–250. дои : 10.1007/BF00264249 . S2CID   27392591 .
• Эллисон, Ллойд (апрель 1989 г.). «Циркулярные программы и самореферентные структуры» . Программное обеспечение: практика и опыт . 19 (2): 99–109. arXiv : 2403.01866 . дои : 10.1002/спе.4380190202 . S2CID   21298473 .
• Герайнт Джонс и Джереми Гиббонс (1992). Алгоритмы дерева в ширину с линейным временем: упражнение по арифметике складок и застежек-молний (технический отчет). Кафедра компьютерных наук Оклендского университета.
• Джон Барвайз ; Лоуренс С. Мосс (июнь 1996 г.). Порочные круги . Центр изучения языка и информации. ISBN  978-1-57586-009-1 . Архивировано из оригинала 21 июня 2010 г. Проверено 24 января 2011 г.
• Лоуренс С. Мосс; Норман Даннер (1997). «Об основах корекурсии». Логический журнал IGPL . 5 (2): 231–257. CiteSeerX   10.1.1.40.4243 . дои : 10.1093/jigpal/5.2.231 .
• Кес Доэтс; Ян ван Эйк (май 2004 г.). Дорога Haskell к логике, математике и программированию . Публикации Королевского колледжа. ISBN  978-0-9543006-9-2 .
• Дэвид Тернер (28 июля 2004 г.). «Тотальное функциональное программирование» . Журнал универсальной информатики . 10 (7): 751–768. дои : 10.3217/jucs-010-07-0751 .
• Джереми Гиббонс; Грэм Хаттон (апрель 2005 г.). «Методы доказательства для корекурсивных программ» . Фундамента информатики . 66 (4): 353–366.
• Леон П. Смит (29 июля 2009 г.), «Корекурсивные очереди Ллойда Эллисона: почему продолжения имеют значение» , The Monad Reader (14): 37–68
• Раймонд Хеттингер (19 ноября 2009 г.). «Рецепт 576961: Техника циклической итерации» .
• М.Б. Смит и Г.Д. Плоткин (1982). «Теоретико-категорное решение рекурсивных уравнений предметной области» (PDF) . SIAM Journal по вычислительной технике . 11 (4): 761–783. дои : 10.1137/0211062 . S2CID   8517995 .
• Леклерк, Франсуа; Полен-Моринг, Кристина (1993). Программирование с использованием потоков в Coq: пример: решето Эратосфена . Типы доказательств и программ: Международный семинар TYPES '93. Springer-Verlag New York, Inc., стр. 191–212. ISBN  978-3-540-58085-0 .