Corecursion

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

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

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

• 1 Примеры
  • 1.1 Факториал
  • 1.2 Последовательность Фибоначчи
  • 1.3 Обход дерева
• 2 Определение
• 3 Обсуждение
• 4 История
• 5 См. Также
• 6 Примечания
• 7 Ссылки

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

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

$n,\; f\; =\; (0,\; 1):\; (n\; +\; 1,\; f\; \times \; (\; n\; +\; 1))\; \{\backslash \; displaystyle\; n,\; f\; =\; (0,1)\; :(\; n\; +\; 1,\; f\; \backslash \; times\; (n\; +\; 1))\}$

или в Haskell,

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

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

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

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

def factorial (n): if n == 0: return 1 else: return n * factorial (n - 1)

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

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

def factorials (): n, f = 0, 1 while True: yield fn, 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! via:

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

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

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

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

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

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

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

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

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

В Haskell

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

Обход дерева

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

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

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

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

$v,\; t\; =\; ([],\; [F\; ull\; T\; ree]):\; (R\; oot\; V\; alues\; (v,\; t),\; C\; hild\; T\; rees\; (t))\; \{\backslash \; 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): if node не None: df (node.left) df (node.right) print (node.value)

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

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

def bf (tree): tree_list = [tree] while tree_list: new_tree_list = для дерева в 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

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

для i в bf (t): print (i)

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

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

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

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

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

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

hd (conc as) = ​​a tl (conc as) = ​​s (sieve ps) = if div p (hd s) затем просеивает p (tl s) else conc (hd s) (sieve p (tl s)) hd (простые числа s) = (hd s) tl (простые числа s) = простые числа (sieve (hd s) (tl s))

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

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

или в Haskell,

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

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

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

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

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

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

из itertools import tee, chain, islice, imap def add (x, y): return x + y def fibonacci (): def deferred_output (): для i на выходе: yield i result, c1, c2 = tee (deferred_output (), 3) paired = imap (add, c1, islice (c2, 1, None)) output = chain ([0, 1], парный) вернуть результат для i в islice (fibonacci (), 20): print (i)

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

fibs = 0: 1: next fibs где next (a: t @ (b: _)) = (a + b): next t

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

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

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

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

дерево данных a b = Leaf a | Ветвь b (Дерево ab) (Дерево ab) bftrav :: Tree ab ->[Дерево ab] bftrav tree = queue, где queue = tree: gen 1 queue gen 0 p = gen len (Leaf _: s) = gen (len- 1) s gen len (Branch _ lr: s) = l: r: gen (len + 1) s

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

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

label :: Tree ab ->Tree Int Int label t = t ′, где (t ′, ns) = go t (1: ns) go :: Tree ab ->[Int] ->(Tree Int Int, [Int]) go (Leaf _) (n: ns) = (Leaf n, n + 1: ns) go (Branch _ lr) (n: ns) = (Branch nl ′ r ′, n + 1: ns ′ ′), Где (l ′, ns ′) = go l ns (r ′, ns ′ ′) = go r ns ′

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

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

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

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