Haskell Language
Рекурсивные схемы

замечания

Фиксированные очки

Fix принимает тип «шаблон» и связывает рекурсивный узел, накладывая шаблон как лазанью.

newtype Fix f = Fix { unFix :: f (Fix f) }

Внутри Fix f мы найдем слой шаблона f . Для того, чтобы заполнить f параметра «s, Fix f пробки в себе. Поэтому, когда вы заглядываете в шаблон f вы обнаруживаете рекурсивное возникновение Fix f .

Вот как типичный рекурсивный тип данных можно перевести в нашу структуру шаблонов и неподвижных точек. Мы удаляем рекурсивные вхождения типа и отмечаем их позиции с использованием параметра r .

{-# LANGUAGE DeriveFunctor #-}

-- natural numbers
-- data Nat = Zero | Suc Nat
data NatF r = Zero_ | Suc_ r deriving Functor
type Nat = Fix NatF

zero :: Nat
zero = Fix Zero_
suc :: Nat -> Nat
suc n = Fix (Suc_ n)


-- lists: note the additional type parameter a
-- data List a = Nil | Cons a (List a)
data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)

nil :: List a
nil = Fix Nil_
cons :: a -> List a -> List a
cons x xs = Fix (Cons_ x xs)


-- binary trees: note two recursive occurrences
-- data Tree a = Leaf | Node (Tree a) a (Tree a)
data TreeF a r = Leaf_ | Node_ r a r deriving Functor
type Tree a = Fix (TreeF a)

leaf :: Tree a
leaf = Fix Leaf_
node :: Tree a -> a -> Tree a -> Tree a
node l x r = Fix (Node_ l x r)

Складывание структуры по одному слою за раз

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

cata :: Functor f => (f a -> a) -> Fix f -> a
cata f = f . fmap (cata f) . unFix

-- list example
foldr :: (a -> b -> b) -> b -> List a -> b
foldr f z = cata alg
    where alg Nil_ = z
          alg (Cons_ x acc) = f x acc

Развертывание структуры по одному слою за раз

Анаморфизмы , или разворачиваются , моделируют примитивную короберизацию. ana создает фиксированную точку за слоем, используя функцию коалгебры (или функцию разворачивания ) для создания каждого нового слоя. ana требует экземпляр Functor для типа шаблона f .

ana :: Functor f => (a -> f a) -> a -> Fix f
ana f = Fix . fmap (ana f) . f

-- list example
unfoldr :: (b -> Maybe (a, b)) -> b -> List a
unfoldr f = ana coalg
    where coalg x = case f x of
                         Nothing -> Nil_
                         Just (x, y) -> Cons_ x y

Обратите внимание, что ana и cata являются двойственными . Типы и реализации являются зеркальными изображениями друг друга.

Развертывание, а затем складывание, сплавление

Обычно формировать программу как создание структуры данных, а затем сворачивать ее на одно значение. Это называется hylomorphism или refold . Для повышения эффективности можно полностью исключить промежуточную структуру.

hylo :: Functor f => (a -> f a) -> (f b -> b) -> a -> b
hylo f g = g . fmap (hylo f g) . f  -- no mention of Fix!

Вывод:

hylo f g = cata g . ana f
         = g . fmap (cata g) . unFix . Fix . fmap (ana f) . f  -- definition of cata and ana
         = g . fmap (cata g) . fmap (ana f) . f  -- unfix . Fix = id
         = g . fmap (cata g . ana f) . f  -- Functor law
         = g . fmap (hylo f g) . f  -- definition of hylo

Примитивная рекурсия

Параморфизмы моделируют примитивную рекурсию. На каждой итерации складки функция складывания получает поддерево для дальнейшей обработки.

para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para f = f . fmap (\x -> (x, para f x)) . unFix

tails Prelude можно моделировать как параморфизм.

tails :: List a -> List (List a)
tails = para alg
    where alg Nil_ = cons nil nil  -- [[]]
          alg (Cons_ x (xs, xss)) = cons (cons x xs) xss  -- (x:xs):xss

Примитивная обработка

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

apo :: Functor f => (a -> f (Either (Fix f) a)) -> a -> Fix f
apo f = Fix . fmap (either id (apo f)) . f

Обратите внимание, что apo и para являются двойственными . Стрелки типа перевернуты; кортеж в para является двойным по отношению к Either в apo , а реализации - зеркальными отображениями друг друга.