deniok

Предыдущие посты этой серии:
1. Типы как неподвижные точки функторов
2. Алгебры и катаморфизмы

( Анаморфизмы и коалгебры ко-под ко-катом ... )

The Origami style is based around the idea that datatypes are fixpoints of shape functors.
(сегодняшний LtU)

Про всё заявленное в теме не напишу, а про это - напишу :)

Общеизвестное :)
Обычная рекурсия

fac n = if n == 0 
           then 1
           else n * fac (n-1)

может быть выражена через комбинатор неподвижной точки fix:

-- нерекурсивный хэлпер
fac' f n = if n == 0 
               then 1 
               else n * f (n-1)
-- рекурсия здесь
fac = fix fac'

Комбинатор неподвижной точки определен так:

fix f = f (fix f)

Аналог fix для типов
А теперь - от обыденного к прекрасному! ;) Можно написать аналог fix для типов:

data Rec f = In (f (Rec f))

где тип f должен быть, ясен пень, полиморфно параметризован (а для дальнейших вкусностей ещё и instance Functor).
Тип конструктора данных для типа Rec

In :: f (Rec f) -> Rec f

дает понять, что это - действительно fix уровня типов.

Теперь мы можем выразить все обычные рекурсивные типы как фиксированные точки функторов.

( Примеры под катом... )

Ссылки:

Bananas in Space - классика жанра :)

Origami programming

Parametric Datatype-Genericity - сегодняшняя новинка (must read!)