Зигоморфизм — генерализация параморфизма, которая повзволяет фолдить структуру с помощью

вспомогательной функции

zygo :: Functor f => Algebra f b -> (f (a, b) -> a) {- следовало бы и здесь алгебру определить -} -> Mu f -> a
zygo f g = fst . cata (g &&& f . fmap snd)

Препроморфизм — катаморфизм с дополнительным естественным преобразованием, которое применяется перед интерпретацией через представленную Ф-алгебру на каждой итерации рекурсивной процедуры

prepro g f = f . (fmap . prepro . cata (Mu . g)) f . out

Постпроморфизм — корекурсивная схема, являющаяся дуализмом к препроморфизму, позволяющая с помощью соответствующего естественного преобразования генерировать коданные.



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

def fac(a):
n, f = 0, 1
while n < a:
n, f = n + 1, f * (n + 1)
yield f

На хаскелле с использованием постпроморфизма

fac = flip postpro stream . phi
where stream = Cons <*> succ
phi _ Nil = Nil
phi n alg@(Cons a b)
| a <= n = alg
| otherwise = Nil

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

histo :: Functor f => CVAlgebra f a -> Mu f -> a
histo f = out >>> fmap phi >>> f where
phi t = (Cofree . Mu .: CoBindF) (histo f t) ((out t) <&> uncofree . phi)

Футуморфизм — дуализм к хистоморфизму, ана на свободной монаде, конструирует Ф-алгебраическую структуру пошагово где коалгебра может вернуть несколько уровней подструктуры одновременно

futu :: Functor f => CVCoalgebra f a -> a -> Mu f
futu f = Mu <<< fmap phi <<< f
where phi (Free(Mu(ReturnF a))) = futu f a
phi (Free(Mu(BindF a))) = (Mu .: fmap) phi a)


* Следует также прочесть
cs.ox.ac.uk/people/daniel.james/sorting/sorting.pdf
cs.ox.ac.uk/people/nicolas.wu/publications/Histomorphisms.pdf
cs.cornell.edu/~jeannin/papers/wf.pdf
citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.125&rep=rep1&type=pdf

† Элгот алгебры
iti.cs.tu-bs.de/~milius/research/elgot_lmcs.pdf
comonad.com/reader/2008/elgot-coalgebras

‡ Насчёт имплементации по Мендлеру
researchgate.net/publication/244249998_Coding_Recursion_a_la_Mendler_Extended_Abstract
researchgate.net/publication/220370687_The_Recursion_Scheme_from_the_Cofree_Recursive_Comonad


Продолжение следует

Статья на эту же тему, правда? https://jtobin.io/time-traveling-recursion