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

Катаморфизмы и алгебры под катом во избежание... )
Продолжение следует...
deniok: (Default)
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!)

Profile

deniok: (Default)
deniok

April 2017

S M T W T F S
      1
23 45678
9101112131415
16171819202122
23242526272829
30      

Syndicate

RSS Atom

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 24th, 2017 03:15 am
Powered by Dreamwidth Studios