import Prelude hiding (length,last,head,tail,concat,fst,zip,unzip)

-- Mixed (recursive) data types:
-- List: empty or one element (integer) + rest list
data List = Empty | Cons Int List
 deriving (Eq,Ord,Show) -- allow printing of lists

list12 :: List
list12 = Cons 1 (Cons 2 Empty)


-- List concatenation (predefined as "++")
append :: List -> List -> List
append Empty       ys = ys
append (Cons x xs) ys = Cons x (append xs ys)

list1212 = append list12 list12

-------------------------------------------------------------------------
-- Polymorphic types:

-- Length of a list:
length :: [a] -> Int
length []       = 0
length (x : xs) = 1 + length xs

-- Computes/returns the last element of a list:
last :: [a] -> Maybe a
last []     = Nothing
last [x]    = Just x
last (x:xs) = last xs


-- Polymorphic trees: each leaf contains some element
data Tree a = Leaf a | Node (Tree a) (Tree a)

tree1234 :: Tree Int
tree1234 = Node (Node (Leaf 1)
                      (Node (Leaf 2)
                            (Leaf 3)))
                (Leaf 4)

-- Compute the height of a tree:
height :: Tree a -> Int
height (Leaf x)     = 1
height (Node t1 t2) = 1 + max (height t1) (height t2)

isNothing :: Maybe a -> Bool
isNothing Nothing = True
isNothing (Just x) = False

-- First element of list:
head :: [a] -> a
head (x:_) = x

-- The rest of a list:
tail :: [a] -> [a]
tail (_:xs) = xs

-- Concatenate a list of lists to one list:
concat :: [[a]] -> [a]
concat []       = []
concat (xs:xss) = xs ++ concat xss

-- Select the n-th element of a list (n=0: head of a list)
nth :: [a] -> Int -> a
--nth (x:xs) n = if n==0 then x
--                       else nth xs (n-1)
nth (x:xs) 0 = x
nth (x:xs) n = nth xs (n-1)
-- predefined as (!!)

-- Returns all ints in a int/string list
allInts :: [Either Int String] -> [Int]
allInts []     = []
allInts (Left x  : xs) = x : allInts xs
allInts (Right _ : xs) = allInts xs

-- The first component of a pair:
fst :: (a,b) -> a
fst (x,y) = x

-- The second component of a pair:
snd :: (a,b) -> b
snd (x,y) = y

-- Zip two lists into a list of pairs:
zip :: [a] -> [b] -> [(a,b)]
zip []     _      = []
zip _      []     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys