module Slides4 where
import Prelude hiding (map,filter,foldr,takeWhile,dropWhile,span,sum,concat)

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

map :: (a-> b)-> [a]-> [b]

map f []     = []
map f (x:xs) = (f x):(map f xs)

filter :: (a-> Bool)-> [a]-> [a]

filter p []   = []
filter p (x:xs) 
  | p x       = x:(filter p xs)
  | otherwise = filter p xs

foldr :: (a-> b-> b)-> b-> [a]-> b

foldr f e []     = e
foldr f e (x:xs) = f x (foldr f e xs)

sum :: [Int]-> Int
sum xs = foldr (+) 0 xs

concat :: [[a]]-> [a]
concat xs = foldr (++) [] xs

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile p []          =  []
takeWhile p (x:xs) 
            | p x       =  x : takeWhile p xs
            | otherwise =  []

dropWhile :: (a -> Bool) -> [a] -> [a]           

dropWhile p []          =  []
dropWhile p xs@(x:xs')
            | p x       =  dropWhile p xs'
            | otherwise =  xs

span      :: (a -> Bool) -> [a] -> ([a],[a])
span p xs = (takeWhile p xs, dropWhile p xs)

ins :: Int-> [Int]-> [Int]  
ins x xs = lessx ++ (x: grteqx) where
  (lessx, grteqx) = span less xs
  less z = z < x

isort :: [Int]-> [Int]
isort xs = foldr ins [] xs

qsortBy :: (a-> a-> Bool)-> [a]-> [a]
qsortBy ord [] = []
qsortBy ord (x:xs) = 
     qsortBy ord [y| y<-xs, ord y x] ++ [x] ++
     qsortBy ord [y| y<-xs, not (ord y x)]