{-# LANGUAGE RankNTypes #-} -- just to enable "forall"
import Prelude hiding (length, (++), head, tail, last, concat, fst, snd, zip, unzip)

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

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

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

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


-- Concatenation of two lists:
(++) :: [a] -> [a] -> [a]
[]       ++ ys = ys
(x : xs) ++ ys = x : (xs ++ ys)

-- Partial values: undefined or just a value
data Partial a = Undefined | Defined a
--data Maybe a = Nothing | Just a

aOne :: Maybe Int
aOne = Just 1

noValue :: Maybe a
noValue = Nothing

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

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

-- Polymorphic binary trees:
data Tree a = Leaf a | Node (Tree a) (Tree a)

tree123 :: Tree Int
tree123 = Node (Leaf 1) (Node (Leaf 2) (Leaf 3))

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


-- Polymorphic lists:
--data [a] = [] | a : [a]  -- [a] === [] a
-- arbitrary list types: [Int]  [[Int]]  [[[Float]]] [Tree Int] [Tree [Float]]

-- Returns the first element of a list:
head :: [a] -> a
head (x:xs) = x

-- Returns possibly the first element of a list:
maybeHead :: [a] -> Maybe a
maybeHead []     = Nothing
maybeHead (x:xs) = Just x

-- Returns the rest of a non-empty list:
tail :: [a] -> [a]
tail (x:xs) = xs

-- Returns possibly the rest of a list:
maybeTail :: [a] -> Maybe [a]
maybeTail []     = Nothing
maybeTail (x:xs) = Just xs

-- The last element of a list:
last :: [a] -> a
last [x]    = x   -- [x] === x : []
last (x:xs) = last xs
--last (x:y:xs) = last (y:xs)

someLists :: [[Int]]
someLists = [ [1,2,3], [4,5], [6,8,9]]

-- Concatenates a list of lists into a single list of elements.
concat :: [[a]] -> [a]
concat []       = []
concat (xs:xss) = xs ++ concat xss

-- type String = [Char]

hello :: String
hello = "Hello!" -- ['H','e','l','l','o','!']

-- Returns 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)
--nth (x:xs) 0 = x
--nth (x:xs) n = nth xs (n - 1)

-- Predefined as (!!)

-- Mixed data types: union of two types
data Union a b = This a | That b

mixedList :: [Union Int Bool]
mixedList = [This 42, That True]

-- data Either a b = Left a | Right b
mixList :: [Either Int (Maybe a)]
mixList = [Left 42, Right Nothing, Left 3]

-- Sum up the integer elements:
sumUp :: [Either Int a] -> Int
sumUp [] = 0
sumUp (Left i  : xs) = i + sumUp xs
sumUp (Right x : xs) = sumUp xs

-- Tuple types:
data Pair a b = Pair a b
data Triple a b c = Triple a b c

--data (a,b) = (a,b)
--data (a,b,c) = (a,b,c)

aPair :: (Int,Bool)
aPair = (42, True)

-- First argument of a pair:
fst :: (a,b) -> a
fst (x,_) = x

-- Second argument of a pair
snd :: (a,b) -> b
snd (_,y) = y

-- Zip two lists to a single list of pairs of corresponding elements.
zip :: [a] -> [b] -> [(a,b)]
zip []     ys     = []
zip xs     []     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

-- Unzip a list of pairs into two lists.
unzip :: [(a,b)] -> ([a],[b])
unzip []     = ([],[])
unzip ((x,y):ps) = let (xs,ys) = unzip ps
                   in (x:xs, y:ys) 
--unzip ((x,y):ps) =  (x:xs, y:ys)  where (xs,ys) = unzip ps