多相再帰の例

gistfile1.hs

data Seq a = Nil | Cons a (Seq (a,a))

-- 多相再帰の型推論は完全ではないので、
-- このように型アノテーションをコメントアウトすると
-- コンパイルできない
-- len :: Seq a -> Int
len Nil = 0
len (Cons x s) = 1 + 2 * (len s)

pair f (x,y) = (f x, f y)

-- mapseq :: (a -> b) -> Seq a -> Seq b
mapseq f Nil = Nil
mapseq f (Cons x xs) = Cons (f x) (mapseq (pair f) xs)

main = return ()