import SimplePrelude hiding (length, last, head, tail, concat)

-- Compute the length of a list of numbers:
lengthInt :: [Int] -> Int
lengthInt []     = 0
lengthInt (x:xs) = 1 + lengthInt xs

-- Compute the length of a list of characters:
lengthChar :: [Char] -> Int
lengthChar []     = 0
lengthChar (x:xs) = 1 + lengthChar xs

-- Compute the length of a list of any type of elements:
length :: [a] -> Int
length []     = 0
length (x:xs) = 1 + length xs

-- Compute the last element of a list:
last :: [a] -> a
last []     = error "last on empty list!"
last [x]    = x
last (x:xs) = last xs


-- Datatype for partial values
-- data Maybe a = Nothing | Just a

-- Compute the last element of a list:
lastP :: [a] -> Maybe a
lastP []     = Nothing
lastP [x]    = Just x
lastP (x:xs) = lastP xs

-- Is a partial value really no value?
isNothing :: Maybe a -> Bool
isNothing Nothing  = True
isNothing (Just x) = False

fromJust :: Maybe a -> a
fromJust (Just x) = x


-- Binary tree: a leaf contains a value, a node has two subtrees
data BTree a = Leaf a | Node (BTree a) (BTree a)
 deriving Show

btree123 :: BTree Int
btree123 = Node (Leaf 1) (Node (Leaf 2) (Leaf 3))

-- Computes the height of a binary tree:
height :: BTree a -> Int
height (Leaf _)     = 1
height (Node t1 t2) = 1 + max (height t1) (height t2)

-- Important functions on lists:

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

-- Remaining list of a non-empty(!) list:
tail :: [a] -> [a]
tail (_:xs) = xs

-- Concatenates a list of list to a single list:
concat :: [[a]] -> [a]
concat []       = []
concat (xs:xss) = xs ++ concat xss

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

-- Sum up all integers in a list of Either Int ...:
sumUp :: [Either Int a] -> Int
sumUp []             = 0
sumUp (Left x  : xs) = x + sumUp xs
sumUp (Right _ : xs) = sumUp xs