2007-12-13

deniok: (Default)
2007-12-13 11:16 pm

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

Продолжаю вести конспект 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
(Говоря про любые рекурсивные типы, я пока оставляю за скобками экспоненциальные, то есть со стрелками внутри конструктора данных.)

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