固定点

Fix 采用模板类型并绑定递归结，将模板分层，如烤宽面条。

newtype Fix f = Fix { unFix::f (Fix f) }

在 Fix f 里面，我们找到了一层模板 f。为了填补 f 的参数，Fix f 在插头本身。因此，当你查看模板 f 时，你会发现 Fix f 的递归发生。

以下是典型的递归数据类型如何转换为模板和固定点的框架。我们删除类型的递归出现并使用 r 参数标记它们的位置。

{-# LANGUAGE DeriveFunctor #-}

-- natural numbers
-- data Nat = Zero | Suc Nat
data NatF r = Zero_ | Suc_ r deriving Functor
type Nat = Fix NatF

zero::Nat
zero = Fix Zero_
suc::Nat -> Nat
suc n = Fix (Suc_ n)

-- lists: note the additional type parameter a
-- data List a = Nil | Cons a (List a)
data ListF a r = Nil_ | Cons_ a r deriving Functor
type List a = Fix (ListF a)

nil::List a
nil = Fix Nil_
cons::a -> List a -> List a
cons x xs = Fix (Cons_ x xs)

-- binary trees: note two recursive occurrences
-- data Tree a = Leaf | Node (Tree a) a (Tree a)
data TreeF a r = Leaf_ | Node_ r a r deriving Functor
type Tree a = Fix (TreeF a)

leaf::Tree a
leaf = Fix Leaf_
node::Tree a -> a -> Tree a -> Tree a
node l x r = Fix (Node_ l x r)