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

-- Integer lists:
-- A type for a list of integers
data IntList = Nil | Cons Int IntList
 deriving Show

data Zahlenliste = Leer | NichtLeer Int Zahlenliste

-- A list with 1,2,3:
l123 :: IntList
l123 = Cons 1 (Cons 2 (Cons 3 Nil))

-- Returns the length of a list:
lengthIntList :: IntList -> Int
lengthIntList Nil         = 0
lengthIntList (Cons x xs) = 1 + lengthIntList xs

{-
lengthIntList (Cons 42 Nil) = 1 + lengthIntList Nil
                            = 1 + 0
                            = 1
-}

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

-- Returns the length of an integer list:
lengthInt :: [Int] -> Int
lengthInt []       = 0
lengthInt (x : xs) = 1 + lengthInt xs

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

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

-- Returns the length of a list containing elements of type 't':
-- t is a type variable
-- polymorphic type: type containing type variables
--length :: forall t . [t] -> Int
length :: [t] -> Int  -- forall is implicit
length []       = 0
length (x : xs) = 1 + length xs

-- Concatenation of two lists, predefined as '++' in the prelude:
(++) :: [a] -> [a] -> [a]
[]       ++ ys = ys
(x : xs) ++ ys = x : (xs ++ ys)

-- Lists containing elements of an arbitrary type:
-- A type for a list of integers
data List a = NilA | ConsA a (List a)
 deriving Show

list12 :: List Int
list12 = ConsA 1 (ConsA 2 NilA) 

------------------------------------------------------------------

-- A data type for partial values:
data Partial a = Undefined | Defined a
-- predefined as:
-- data Maybe a = Nothing | Just a

value1 :: Partial Int
value1 = Defined 1

noValue :: Partial a
noValue = Undefined

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

valueOf :: Partial a -> a
valueOf (Defined x) = x

------------------------------------------------------------------

-- A binary tree structure:
data Tree a = Leaf a | Node (Tree a) (Tree a)

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

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

------------------------------------------------------------------

-- Polymorphic lists as defined in Haskell:
-- data [a] = [] | a : [a]

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

maybeHead :: [a] -> Maybe a
maybeHead []     = Nothing
maybeHead (x:xs) = Just x

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

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

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

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

-- Strings:
--type String = [Char]

hello :: String
hello = "Hello"


------------------------------------------------------------------

-- Union types:
data Union a b = This a | That b

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

-- Returns the sum of all integer elements in a mixed list:
sumInts :: [Union Int a] -> Int
sumInts []      = 0
sumInts (This x : xs) = x + sumInts xs
sumInts (That x : xs) = sumInts xs