固定點

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)