Учебник по Haskell

перь класс перестал быть воображаемым, он стал типом с параметром. Результатом функции свёртки будет

функция из рекурсивного типа Fix f в тип параметр.

Аналогично строится и функция unfold:

unfold :: (b -> f b) -> (b -> Fix f)

В первой функции мы указываем один шаг разворачивания рекурсивного типа, а функция развёртки

рекурсивно распространяет этот один шаг на потенциально бесконечную последовательность применений

этого одного шага.

Теперь давайте определим эти функции. Но для этого нам понадобится от типа f одно свойство. Он

должен быть функтором, опираясь на это свойство, мы будем рекурсивно обходить этот тип.

fold :: Functor f => (f a -> a) -> (Fix f -> a)

fold f = f . fmap (fold f) . unFix

Проверим эту функцию по типам. Для этого нарисуем схему композиции:

f

fmap (fold f)

f

Fix f

f (Fix f)

f a

a

Сначала мы разворачиваем обёртку Fix и получаем значение типа f (Fix f), затем с помощью fmap мы

внутри типа f рекурсивно вызываем функцию свёртки и в итоге получаем значение f a, на последнем шаге

мы выполняем свёртку на текущем уровне вызовом функции f.

Аналогично определяется и функция unfold. Только теперь мы сначала развернём первый уровень, затем

рекурсивно вызовем развёртку внутри типа f и только в самом конце завернём всё в тип Fix:

unfold :: Functor f => (a -> f a) -> (a -> Fix f)

unfold f = Fix . fmap (unfold f) . f

Схема композиции:

Fix

fmap (unold f)

f

Fix f

f (Fix f)

f a

a

Возможно вы уже догадались о том, что функция fold дуальна по отношению к функции unfold, это

особенно наглядно отражается на схеме композиции. При переходе от fold к unfold мы просто перевернули

все стрелки заменили разворачивание типа Fix на заворачивание в Fix.

Определим несколько функций для натуральных чисел и списков в стиле оригами. Для начала сделаем

L и N экземпляром класса Functor:

instance Functor N where

fmap f x = case x of

Zero

-> Zero

Succ a

-> Succ (f a)

instance Functor (L a) where

fmap f x = case x of

Nil

-> Nil

Cons a b

-> Cons a (f b)

Это всё что нам нужно для того чтобы начать пользоваться функциями свёртки и развёртки! Определим

экземпляр Num для натуральных чисел:

instance Num Nat where

(+) a = fold $ \x -> case x of

Zero

-> a

Succ x

-> succ x

(*) a = fold $ \x -> case x of

242 | Глава 16: Категориальные типы

Zero

-> zero

Succ x

-> a + x

fromInteger = unfold $ \n -> case n of

0

-> Zero

n

-> Succ (n-1)

abs = undefined

signum = undefined

Сложение и умножение определены через свёртку, а функция построения натурального числа из чис-

ла типа Integer определена через развёртку. Сравните с теми функциями, которые мы писали в главе про

структурную рекурсию. Теперь мы не передаём отдельно две функции, на которые мы будем заменять кон-

структоры. Эти функции закодированы в типе с параметром. Для того чтобы этот код заработал нам придётся

добавить ещё одно расширение TypeSynonymInstances наши рекурсивные типы являются синонимами, а не

новыми типами. В рамках стандарта Haskell мы можем определять экземпляры только для новых типов, для

того чтобы обойти это ограничение мы добавим ещё одно расширение.

*Fix> succ $ 1+2

(Succ (Succ (Succ (Succ (Zero)))))

*Fix> ((2 * 3) + 1) :: Nat

(Succ (Succ (Succ (Succ (Succ (Succ (Succ (Zero))))))))

*Fix> 2+2 == 2*(2::Nat)

True

Определим функции на списках. Для начала определим две вспомогательные функции, которые извле-

кают голову и хвост списка:

headL :: List a -> a

headL x = case unFix x of

Nil

-> 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