A new list type

module XList where
 
import Prelude hiding (length, head, tail, foldr, foldl, map, zip, zipWith, replicate)
 
data List t = Node {length_ :: Int, head :: t, tail :: List t} | End   deriving (Eq, Show)
 
length End = 0
length n   = length_ n
 
infixr 5 #:
 
x #: xs = Node (1 + length xs) x xs
 
foldr _ v (End)         = v
foldr f v (Node _ x xs) = f x (foldr f v xs)
 
foldl _ v (End)         = v
foldl f v (Node _ x xs) = foldl f (v `f` x) xs
 
foldl' _ v (End)         = v
foldl' f v (Node _ x xs) = (foldl' f $! v `f` x) xs
 
map _ (End)         = End
map f (Node n x xs) = Node n (f x) (map f xs)
 
zipWith f (End) _ = End
zipWith f _ (End) = End
zipWith f (Node n0 x xs) (Node n1 y ys) = Node (n0 `min` n1) (f x y) (zipWith f xs ys)
 
zip = zipWith (\x y -> (x,y))
 
join (End)         ys = ys
join (Node n x xs) ys = Node (n + length ys) x (join xs ys)
 
merge = foldr join End
 
select _ End = End
select f (Node n x xs) = case f x of
  True  -> x #: select f xs
  False -> select f xs
 
replicate 0 _ = End
replicate n x = Node n x (replicate (n-1) x)