Какая связь между примитивной рекурсией и катаморфизмами? - PullRequest
Новая
       95

Какая связь между примитивной рекурсией и катаморфизмами?

13 голосов
/ 20 июня 2020

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

cataNat :: b -> (b -> b) -> Natural -> b
cataNat zero succ = go
  where
    go n = if (n <= 0) then zero else succ (go (n - 1))

fib :: Natural -> Natural
fib = fst . cataNat (0, 1) (\(a, b) -> (b, a + b))

cataNat для меня похоже на примитивную рекурсию. По крайней мере, каждое приложение кажется гарантированно завершенным, независимо от того, какая комбинация zero и succ предоставлена. На каждой итерации общая проблема разбивается на наименьшие / простейшие экземпляры проблемы. Так что, даже если это технически не примитивная рекурсия, она кажется столь же выразительной. Если это правда, это будет означать, что катаморфизма недостаточно для express общей рекурсии. Для этого нам, вероятно, понадобится гиломорфизм. Верны ли мои рассуждения, то есть справедливо ли равенство для любого типа катаморфизма, а не только для натуральных чисел?

1 Ответ

5 голосов
/ 20 июня 2020

Примитивная рекурсия напрямую соответствует параморфизму.

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

cata :: b -> (a -> b -> b) -> [a] -> b
cata = flip foldr -- I'm lazy, but this argument order makes a bit more sense for this example

para :: b -> (a -> [a] -> b -> b) -> [a] -> b
para z _ []     = z
para z f (x:xs) = f x xs (para z f xs)

-- Removes the first element from the list which is equal to the other argument
delete1 :: Eq a => a -> [a] -> [a]
delete1 x xs = cata (const []) (\el k found -> if not found && el == x then k True else el : k found) xs False

-- Removes the first element from the list which is equal to the other argument
delete2 :: Eq a => a -> [a] -> [a]
delete2 x xs = para [] (\el raw processed -> if el == x then raw else el : processed) xs

Посмотрите, насколько неудобно delete1 по сравнению с delete2. Вы не только должны исказить лог c, превратив результат cata в функцию, но и получите очень реальные эксплуатационные расходы. Вы должны пройти все в списке после нахождения подходящего элемента и заново создать все конструкторы (:). Это может иметь заметные затраты на эффективность. Для сравнения, delete2, когда он находит целевой элемент, может просто использовать существующий конец списка для остатка, даже не глядя на него. Конечно, в большинстве случаев использования foldr (в реальном мире, а не в этом примере) не создается функция и не требуется доступ к необработанному концу списка. Для них катаморфизм будет немного более эффективным просто из-за передачи меньшего количества данных.

Так что с точки зрения теоретической мощности они эквивалентны. С практической точки зрения каждый из них имеет свое применение, хотя катаморфизмы встречаются гораздо чаще.

Для некоторого расширения идеи в более общих терминах см. Библиотеку рекурсивных схем . Он использует довольно иную формулировку идеи, так что он может абстрагироваться от типов данных с разными формами, вместо того, чтобы нуждаться в другом типе для cata / para для каждого типа данных, к которому они могут применяться. Но на самом деле это просто альтернативный способ объединения тех же идей, и другие виды морфизмов также охватываются, в том числе больше ниша (или даже возможно бесполезно ) ед.

...