Алгебры и катаморфизмы

Продолжаю вести конспект Bananas in Space (начало здесь).

Краткое содержание первой серии

С помощью аналога fix для типов:

-- конструктор типа
data Rec f = In (f (Rec f))
-- тип конструктора данных
In :: f (Rec f) -> Rec f

мы научились представлять любые рекурсивные типы, скажем

-- классическая запись рекурсивного типа
data Nat = Z | S Nat

как неподвижные точки функторов

-- добавляем параметр под рекурсию ...
data N c = Z | S c
-- ... делаем функтором ...
instance Functor N where
  fmap g  Z    = Z
  fmap g (S x) = S (g x)
-- ... и получаем альтернативную запись рекурсивного типа Nat
type Nat = Rec N

(Говоря про любые рекурсивные типы, я пока оставляю за скобками экспоненциальные, то есть со стрелками внутри конструктора данных.)

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

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