import Prelude hiding (flip, map, foldr, foldl, filter, sum)
import Data.Char ( chr, ord )

-- The derivative of a function (for small dx):
derive :: (Float -> Float) -> (Float -> Float)
derive f = f'
 where f' x = (f (x + dx) - f x) / dx

dx :: Float
dx = 0.001

square :: Float -> Float
square x = x * x


add1 :: Float -> Float -> Float
add1 x y = x+y

--add2 :: Float -> (Float -> Float)
add2 :: Float -> Float -> Float
add2 x = \y -> x+y

add3 :: (Float -> Float -> Float)
add3 = \x y -> x+y


-- Currying:
take42 :: [a] -> [a]
take42 = take 42

-- Increment function:
inc :: Int -> Int
inc = (+) 1

-- Decrement function:
dec :: Int -> Int
dec = (+ (-1))


flip :: (a -> b -> c) -> (b -> a -> c)
--flip f = \x y -> f y x
flip f x y = f y x

takeDigits :: Int -> String
takeDigits = (flip take) "0123456789"
--takeDigits = \n -> take n "0123456789"

---------------------------------------------------------------------
-- Generic programming:

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

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

-- Encode a string:
codeString :: String -> String
codeString ""     = ""
codeString (c:cs) = code c : codeString cs

-- Common structure:
map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = (f x) : map f xs

incList' = map (+ 1)
codeString' = map code


-- Sums all element of an integer list:
sum :: [Int] -> Int
sum []     = 0
sum (x:xs) = x + sum xs

-- Check sum of a string:
checkSum :: String -> Int
checkSum ""     = 0
checkSum (c:cs) = ord c + checkSum cs

-- Common scheme:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f c []     = c
foldr f c (x:xs) = f x (foldr f c xs)

sum' = foldr (+) 0
checkSum' = foldr (\c x -> ord c + x) 0


-- Filters elements of a list:
filter :: (a -> Bool) -> [a] -> [a]
filter p []                 = []
filter p (x:xs) | p x       = x : filter p xs
                | otherwise = filter p xs

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

-- List to set, i.e., remove all dupolicate elements in a list:
nub :: [Int] -> [Int]
nub []     = []
nub (x:xs) = x : nub (filter (/= x) xs)

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


-- foldl: accumulator
sumL :: [Int] -> Int
sumL xs = sumL' xs 0
 where sumL' [] s = s
       sumL' (x:xs) s = sumL' xs (s+x)

foldl f a [] = a
foldl f a (x:xs) = foldl f (f a x) xs