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

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

-- Squares all elements in a list
sqList :: [Int] -> [Int]
sqList []     = []
sqList (x:xs) = (x*x) : sqList xs

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

-- encodes every character in a string
codeStr :: String -> String
codeStr []     = ""
codeStr (c:cs) = code c : codeStr cs

-- Apply a function f on every element in 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)
codeStr' = map code

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

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

-- Sums up the codes of all elements in a string
checkSum :: String -> Int
checkSum []     = 0
checkSum (c:cs) = ord c + checkSum cs

-- Multiplies all elements in a list
prod :: [Int] -> Int
prod []     = 1
prod (x:xs) = x * prod xs

-- Multiplies all elements in a 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
prod' = foldr (*) 1
checkSum' = foldr (\x y -> ord x + y) 0

----------------------------------------------------------------------------
-- Filters elements in a list satisfying a predicate
filter :: (a -> Bool) -> [a] -> [a]
filter _ []     = []
filter p (x:xs) | p x       = x : filter p xs
                | otherwise = filter p xs

-- Transforms a list into a set, i.e., delete duplicate elements
nub :: [Int] -> [Int]
nub []     = []
nub (x:xs) = x : nub (filter (/= x) xs)

-- Sorts a list with the quicksort algorithm
qsort :: [Int] -> [Int]
qsort []     = []
qsort (x:xs) = qsort (filter (<= x) xs) ++ [x] ++ qsort (filter (> x) xs)


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

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

sumAcc xs = sum' 0 xs
 where sum' e []     = e
       sum' e (x:xs) = sum' (e + x) xs

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f e []     = e
foldl f e (x:xs) = foldl f (f e x) xs

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