多相再帰型

Data.Sequence で使われている FingerTree の構造を調べていて、多相再帰型を初めて知った。僕が思いつく最も簡単な例はこう。

data Bin a = Bin a a deriving Show
data List a = Nil | Cons a (List (Bin a)) deriving Show

こういう風に使う。

→ Nil
Nil
→ Cons 1 Nil
Cons 1 Nil
→ Cons 1 $ Cons (Bin 2 3) Nil
Cons 1 (Cons (Bin 2 3) Nil)
→ Cons 1 $ Cons (Bin 2 3) $ Cons (Bin (Bin 4 5) (Bin 6 7)) Nil
Cons 1 (Cons (Bin 2 3) (Cons (Bin (Bin 4 5) (Bin 6 7)) Nil))