Corecursion - Corecursion

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

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

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

Примеры

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

Факториал

Классическим примером рекурсии является вычисление факториала , который рекурсивно определяется как 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 . В этом примере функция возвращает единственное значение.

Это раскручивание стека может быть объяснено, определяя факториал corecursively , как итератор , где один начинается со случая , затем из этого начального значения конструируются факториальные значения для увеличения чисел 1, 2, 3 ... как в приведенном выше рекурсивном определении с "стрела времени" как бы перевернутая, прочитав ее в обратном направлении как . Corecursive алгоритм , таким образом , определяется производит поток из всех факториалов. Это может быть конкретно реализовано как генератор . Символически, отмечая, что вычисление следующего факториала требует отслеживания как n, так и f (предыдущего факториала), это можно представить как: ${\ displaystyle 1 =: 0!}$${\ Displaystyle п! \ раз (п + 1) = :( п + 1)!}$

${\ Displaystyle п, е = (0,1) :( п + 1, е \ раз (п + 1))}$

или в Haskell ,

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

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

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

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

def factorial(n):
    """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(k):
    n, f = 0, 1
    while n <= k:
        yield f
        n, f = n + 1, f * (n + 1)

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

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

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

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

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

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

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

${\ displaystyle a, b = (0,1) :( b, a + b)}$

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

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

В Haskell,

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

Обход дерева

Обход дерева с использованием подхода в глубину - классический пример рекурсии. Соответственно, обход в ширину вполне естественно можно реализовать с помощью corecursion.

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

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

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

${\ displaystyle v, t = ([], [FullTree]) :( RootValues ​​(v, t), ChildTrees (t))}$

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

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

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

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

В 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 , то конечные типы совпадают с начальными типами, а соответствующие конечная коалгебра и начальная алгебра образуют изоморфизм.

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

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

Обсуждение

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

В «Программировании с потоками в 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 к нему) и чисел, последовательно просеиваемых потоками, может быть представлена ​​как

${\ displaystyle p, s = (0, [2 ..]) :( hd (s), решето (hd (s), tl (s)))}$

или в Haskell,

(\(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, imap

def add(x, y):
    return x + y

def fibonacci():
    def deferred_output():
        for i in output:
            yield i
    result, c1, c2 = tee(deferred_output(), 3)
    paired = imap(add, c1, islice(c2, 1, None))
    output = chain([0, 1], paired)
    return result

for i in islice(fibonacci(), 20):
    print(i)

Определение 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)

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

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

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

bftrav :: Tree a b -> [Tree a b]
bftrav tree = queue
  where
    queue = tree : gen 1 queue

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

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

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

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

    go :: Tree a b    -> [Int]  -> (Tree Int Int, [Int])
    go   (Leaf   _    ) (n:ns) = (Leaf   n       , n+1 : ns  )
    go   (Branch _ l r) (n:ns) = (Branch n l′ r′ , n+1 : ns′′)
                                where
                                  (l′, ns′ ) = go l ns
                                  (r′, ns′′) = go r ns′

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

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

История

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

Смотрите также

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

Ноты

Рекомендации