-> error ”empty list”
Cons a _
-> a
tailL :: List a -> List a
tailL x = case unFix x of
Nil
-> error ”empty list”
Cons a b
-> b
Теперь определим несколько новых функций:
mapL :: (a -> b) -> List a -> List b
mapL f = fold $ \x -> case x of
Nil
-> nil
Cons a b
-> f a ‘cons‘ b
takeL :: Int -> List a -> List a
takeL = curry $ unfold $ \(n, xs) ->
if n == 0 then Nil
else Cons (headL xs) (n-1, tailL xs)
Сравните эти функции с теми, что мы определяли в главе о структурной рекурсии. Проверим работают
ли эти функции:
*Fix> :r
[1 of 1] Compiling Fix
( Fix. hs, interpreted )
Ok, modules loaded: Fix.
*Fix> takeL 3 $ iterateL (+1) zero
(Cons (Zero) (Cons (Succ (Zero)) (Cons (Succ (Succ (Zero))) (Nil))))
*Fix> let x = 1 ‘cons‘ 2 ‘cons‘ 3 ‘cons‘ nil
*Fix> mapL (+10) $ x ‘concatL‘ x
(Cons 11 (Cons 12 (Cons 13 (Cons 11 (Cons 12 (Cons 13 (Nil)))))))
Обратите внимание, на то что с большими буквами мы пишем Cons и Nil когда хотим закодировать
функции для свёртки-развёртки, а с маленькой буквы пишем значения рекурсивного типа. Надеюсь, что вы
разобрались на примерах как устроены функции fold и unfold, потому что теперь мы перейдём к теории,
которая за этим стоит.
Программирование в стиле оригами | 243
16.2 Индуктивные и коиндуктивные типы
С точки зрения теории категорий функция свёртки является катаморфизмом, а функция развёртки – ана-
морфизмом. Напомню, что катаморфизм – это функция которая ставит в соответствие объектам категории
с начальным объектом стрелки, которые начинаются из начального объекта, а заканчиваются в данном объ-
екте. Анаморфизм – это перевёрнутый наизнанку катаморфизм.
Начальным и конечным объектом будет рекурсивный тип. Вспомним тип свёртки:
fold :: Functor f => (f a -> a) -> (Fix f -> a)
Функция свёртки строит функции, которые ведут из рекурсивного типа в произвольный тип, поэтому в
данном случае рекурсивный тип будет начальным объектом. Функция развёртки строит из произвольного
типа данный рекурсивный тип, на языке теории категорий она строит стрелку из произвольного объекта в
рекурсивный, это означает что рекурсивный тип будет конечным объектом.
unfold :: Functor f => (a -> f a) -> (a -> Fix f)
Категории, которые определяют рекурсивные типы таким образом называются (ко)алгебрами функторов.