newtype Fix f = Fix { unFix :: f (Fix f) }
В этой записи мы получаем уравнение неподвижной точки Fix f = f (Fix f), где f это некоторый тип
с параметром. Определим тип целых чисел:
240 | Глава 16: Категориальные типы
data N a = Zero | Succ a
type Nat = Fix N
Теперь создадим несколько конструкторов:
zero :: Nat
zero = Fix Zero
succ :: Nat -> Nat
succ = Fix . Succ
Сохраним эти определения в модуле Fix. hs и посмотрим в интерпретаторе на значения и их типы, ghc не
сможет вывести экземпляр Show для типа Fix, потому что он зависит от типа с параметром, а не от конкретно-
го типа. Для решения этой проблемы нам придётся определить экземпляры вручную и подключить несколько
расширений языка. Помните в главе о ленивых вычислениях мы подключали расширение BangPatterns? Нам
понадобятся:
{-# Language FlexibleContexts, UndecidableInstances #-}
Теперь определим экземпляры для Show и Eq:
instance Show (f (Fix f)) => Show (Fix f) where
show x = ”(” ++ show (unFix x) ++ ”)”
instance Eq (f (Fix f)) => Eq (Fix f) where
a == b = unFix a == unFix b
Определим списки-оригами:
data L a b = Nil | Cons a b
deriving (Show)
type List a = Fix (L a)
nil :: List a
nil = Fix Nil
infixr 5 ‘cons‘
cons :: a -> List a -> List a
cons a = Fix . Cons a
В типе L мы заменили рекурсивный тип на параметр. Затем в записи List a = Fix (L a) мы произ-
водим замыкание по параметру. Мы бесконечно вкладываем тип L a во второй параметр. Так получается
рекурсивный тип для списков. Составим какой-нибудь список:
*Fix> :r
[1 of 1] Compiling Fix
( Fix. hs, interpreted )
Ok, modules loaded: Fix.
*Fix> 1 ‘cons‘ 2 ‘cons‘ 3 ‘cons‘ nil
(Cons 1 (Cons 2 (Cons 3 (Nil))))
Спрашивается, зачем нам это нужно? Зачем нам записывать рекурсивные типы через тип Fix? Оказыва-
ется при такой записи мы можем построить универсальные функции fold и unfold, они будут работать для
любого рекурсивного типа.
Помните как мы составляли функции свёртки? Мы строили воображаемый класс, в котором сворачивае-
мый тип заменялся на параметр. Например для списка мы строили свёртку так:
class [a] b where
(:) :: a -> b -> b
[]
:: b