{-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-}
module List where
data N a = N
data List t => C t a = C { hd::a, tl::t a }
instance Show (N a) where
show N = "<>"
instance (List t, Show a, Show (t a)) => Show (C t a) where
show (C x r) = let r' = tail (show r)
in case r' of
">" -> "<" ++ show x ++ ">"
_ -> "<" ++ show x ++ "," ++ r'
instance Functor N where
fmap f N = N
instance (List t, Functor t) => Functor (C t) where
fmap f (C x xs) = C (f x) (fmap f xs)
class List t where
len :: t a -> Int
zipW :: (a->b->c) -> t a -> t b -> t c
foldL :: (a->b->a) -> a -> t b -> a
insert :: Ord a => a -> t a -> C t a
sort :: Ord a => t a -> t a
instance List N where
len N = 0
zipW f N N = N
foldL f e N = e
insert x N = C x N
sort N = N
instance List t => List (C t) where
len (C _ s) = 1 + len s
zipW f (C x s) (C y t) = C (f x y) (zipW f s t)
foldL f e (C x s) = foldL f (f e x) s
insert x (C y s) | x<=y = C x (C y s)
| x> y = C y (insert x s)
sort (C x s) = insert x (sort s)