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

-- predefined:
-- data [Int] = [] | Int : [Int]
-- data [Bool] = [] | Bool : [Bool]
-- data [Char] = [] | Char : [Char]

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

-- Computes the length of a list of booleans.
lengthBool :: [Bool] -> Int
lengthBool []     = 0
lengthBool (x:xs) = 1 + lengthBool xs

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

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

(++) :: [a] -> [a] -> [a]
[]       ++ ys = ys
(x : xs) ++ ys = x : (xs ++ ys)

-- predefined: [a] denotes ([] a)
-- data [a] = [] | a : [a]

-- A type for potentially undefined values:
data Partial a = Undefined | Defined a
 deriving Show

aOne :: Partial Int
aOne = Defined 1

noValue :: Partial a -> Bool
noValue Undefined   = True
noValue (Defined x) = False

-- predefined:
--data Maybe a = Nothing | Just a

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

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


-- Binary trees over some type of elements:
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 binary tree:
height :: Tree a -> Int
height (Leaf x)     = 1
height (Node t1 t2) = 1 + max (height t1) (height t2)

-- Some list operations (predefined!):

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

-- A total definition of head:
maybeHead :: [a] -> Maybe a
maybeHead (x : xs) = Just x
maybeHead []       = Nothing

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

-- Last element of a list.
last :: [a] -> a
last [x]      = x  -- [x] == x : []
last (x : xs) = last xs

-- Concatenates all lists in a list:
concat :: [ [a] ] -> [a]
concat []       = []
concat (xs:xss) = xs ++ concat xss

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

nth' :: [a] -> Int -> a
nth' (x:xs) 0 = x
nth' (x:xs) n = nth' xs (n - 1)

-- predefined as (!!)

-- Strings:
hello :: String
hello = "Hello "

world :: String
world = "world!"

-- Union types:
data Union a b = This a | That b
-- predefined as:
-- data Either a b = Left a | Right b

oneTrue :: [Union Int Bool]
oneTrue = [This 1, That True]

oTrue :: [Either Int Bool]
oTrue = [Left 1, Right True]

intSum :: [Either Int a] -> Int
intSum [] = 0
intSum (Left i : xs) = i + intSum xs
intSum (Right x : xs) = intSum xs

-- Tupel:
-- data (a,b) = (a,b) -- pairs
-- data (a,b,c) = (a,b,c) -- triples
-- ...

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

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

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

-- zip two lists to a pair of lists:
zip :: [a] -> [b] -> [(a,b)]
zip []     ys     = []
zip xs     []     = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys

-- unzip :: [(a,b)] -> ...?