Unknown - haskell-notes

Теперь методы класса с параметром это наши конструкторы исходных классов, а рекурсивный тип записан

через Fix. Если мы сопоставим два способа, то мы сможем получить такой тип для функции свёртки:

fold ::(f b ->b) ->( Fixf ->b)

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

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

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

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

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

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

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

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

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

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

fold :: Functorf =>(f a ->a) ->( Fixf ->a)

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

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

f

fmap (fold f)

f

Fix f

f (Fix f)

f a

a

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

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

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

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

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

unfold :: Functorf =>(a ->f a) ->(a -> Fixf)

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 = casex of

Zero

-> Zero

Succa

-> Succ(f a)

instance Functor( La) where

fmap f x = casex of

Nil

-> Nil

Consa b

-> Consa (f b)

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

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

instance Num Nat where

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

Zero

->a

Succx

->succ x

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

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

Zero

->zero

Succx

->a +x

fromInteger =unfold $\n -> casen 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