import SimplePrelude hiding (map, foldr, filter, foldl, sum)

-- Increments all numbers in a list.
incList :: [Int] -> [Int]
incList []     = []
incList (x:xs) = (x+1) : incList xs

-- Computes the square of all numbers in a list.
sqList :: [Int] -> [Int]
sqList []     = []
sqList (x:xs) = (x*x) : sqList xs

-- Encodes a string as an unreadable string
codeList :: String -> String
codeList ""     = ""
codeList (c:cs) = code c : codeList cs

code :: Char -> Char
code c | ord c == ord 'Z' = 'A'
       | ord c == ord 'z' = 'a'
       | otherwise        = chr (ord c + 1)

-- Generalization: apply some function to all elements of a list:
map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = (f x) : map f xs

incList'  = map (+1)

sqList'   = map (\x -> x*x)

codeList' = map code


-- Sums up all elements of a list of numbers.
sum :: [Int] -> Int
sum []     = 0
sum (x:xs) = x + sum xs

-- Check sum function for a string.
checkSum :: String -> Int
checkSum []     = 1
checkSum (c:cs) = ord c + checkSum cs

-- Generalization: fold all elements of a list into one w.r.t. some
-- binary operation and a value for the empty list.
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f e []     = e
foldr f e (x:xs) = f x (foldr f e xs)

sum' = foldr (+) 0

checkSum' = foldr (\x y -> ord x + y) 1

-- Sums up all elements of a list of numbers with an accumulator
sumI :: [Int] -> Int
sumI xs = sumI' xs 0
 where
  sumI' []     s = s
  sumI' (x:xs) s = sumI' xs (s + x)

-- Generalization: fold all elements of a list into one w.r.t. some
-- binary operation and a value for the empty list in a left-associative manner.
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f e []     = e
foldl f e (x:xs) = foldl f (f e x) xs

sumI' = foldl (+) 0


-- Third scheme: filter elements in a list according to some predicate
filter :: (a -> Bool) -> [a] -> [a]
filter p []     = []
filter p (x:xs) | p x       = x : filter p xs
                | otherwise = filter p xs


-- Map a list of numbers into a list without duplicates
nub :: [Int] -> [Int]
nub []     = []
nub (x:xs) = x : nub (filter (/=x) xs)

-- Quicksort on list of numbers
qsort :: [Int] -> [Int]
qsort []     = []
qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs)


-- filter with foldr:
filter' p = foldr (\x ys -> if p x then x:ys else ys) []

-- Control structure: while:
while :: (a -> Bool) -> (a -> a) -> a -> a
while p f x | p x       = while p f (f x)
            | otherwise = x