List

data List a = Empty | Data a (List a) deriving (Show, Read, Eq, Ord)

new :: a -> List a
new x = Data x Empty

append :: (List a) -> a -> List a
append Empty x = new x
append (Data x l) y = Data x (append l y)

insert :: (Ord a) => (List a) -> a -> List a
insert Empty x = new x
insert (Data x l) y
    | x == y = Data x (Data y l)
    | x <  y = Data x (insert l y)
    | x >  y = Data y (Data x l)

contains :: (Eq a) => (List a) -> a -> Bool
contains Empty _ = False
contains (Data x l) y
    | x == y    = True
    | otherwise = contains l y