Схема рекурсии от Int -> Int?
Фолд идентичность
foldr (:) []
В более общем случае, с помощью сгибов вы можете либо разрушить структуру и получить итоговое значение, либо внедрить структуру таким образом, чтобы получилась одна и та же структура вывода.
[Int] -> [Int]или же [Int] -> Intили же[Int] -> ?
Мне интересно, существует ли похожая идентичность с unfoldr/l.
Я знаю как получить
Int -> [Int]
с развернуть / ана.
Я ищу какой-то путь от
Int -> Int
с рекурсивной схемой.
2 ответа
Исходя из вашего замечания о факториалах, мы можем заметить, что натуральные числа можно рассматривать как рекурсивную структуру данных:
data Nat = Zero | Succ Nat
С точки зрения механизма рекурсивных схем соответствующий базовый функтор будет:
data NatF a = ZeroF | SuccF a
deriving (Functor)
NatFоднако изоморфен Maybe, Таким образом, рекурсивные схемы удобно Maybe базовый функтор Natural Тип с базы. Например, вот тип ana специализируется на Natural:
ana @Natural :: (a -> Maybe a) -> a -> Natural
Мы можем использовать его, чтобы написать личность для Natural:
{-# LANGUAGE LambdaCase #-}
import Numeric.Natural
import Data.Functor.Foldable
idNatAna :: Natural -> Natural
idNatAna = ana $ \case
0 -> Nothing
x -> Just (x - 1)
Коалгебра, которую мы только что дали ana является project заNatural, project будучи функцией, которая разворачивает один слой рекурсивной структуры. В терминах словаря рекурсивных схем, ana project разворачивается личность, и cata embed это сгиб идентичности. (Особенно, project для списков есть uncons от Data.Listза исключением того, что он закодирован ListF вместо Maybe.)
Кстати, факториальная функция может быть выражена как параморфизм натуралов ( как указано в примечании в конце этого вопроса). Мы также можем реализовать это в терминах рекурсивных схем:
fact :: Natural -> Natural
fact = para $ \case
Nothing -> 1
Just (predec, prod) -> prod * (predec + 1)
para делает доступным на каждом рекурсивном шаге оставшуюся часть структуры, которую нужно сложить (если бы мы складывали список, это был бы его хвост). В этом случае я назвал значение, предоставленное таким образом predec потому что на nрекурсивный шаг снизу вверх predec является n - 1,
Обратите внимание, что пользовательский гиломорфизм, вероятно, является более эффективной реализацией, если вам не безразлично это. (Я не тестировал их, хотя.)
Схема рекурсии, которая имеет дело с созданием промежуточной структуры и сносом ее так, чтобы структура не появлялась на входе или выходе, является гильоморфизмом, записанным по буквам hylo в recursion-schemes,
Чтобы использовать hylomorphism, вам нужно указать алгебру (то, что потребляет один шаг рекурсивной структуры) и коалгебру (то, что производит один шаг рекурсивной структуры), и вам нужно иметь тип данных для типа структуры вы используете, конечно.
Вы предложили факториал, поэтому давайте посмотрим, как написать это как hylomorphism.
Один из способов взглянуть на факториал - это произведение списка чисел с обратным отсчетом от начального n, В этом кадре мы можем думать о продукте как о нашей алгебре, снося список по одному минусу за раз, а обратный отсчет как о нашей коалгебре, составляя список как n уменьшается.
recursion-schemes дает нам ListF в качестве удобного базового функтора для списков, поэтому мы будем использовать его в качестве типа данных, создаваемых коалгеброй и потребляемых алгеброй. Его конструкторы Nil а также Consкоторые, конечно, напоминают конструкторы для полных списков, за исключением того, что ListFкак и любая базовая структура в схеме рекурсии, использует параметр типа в месте, где списки будут использовать реальную рекурсию (это означает, что Cons :: a -> b -> ListF a b вместо (:) :: a -> [a] -> [a]).
Так что это определяет наши типы. Сейчас определяю fact это довольно заполняющее упражнение:
import Prelude hiding (product)
import Data.Functor.Foldable
product :: ListF Int Int -> Int
product Nil = 1
product (Cons a b) = a * b
countDown :: Int -> ListF Int Int
countDown 0 = Nil
countDown n = Cons n (n - 1)
fact :: Int -> Int
fact = hylo product countDown