--------------------------------------------------------------------------------
-- returns list in 2nd argument filtered by predicate in 1st argument
filter1 :: (a -> Bool) -> [a] -> [a]
filter1 pred []     = []
filter1 pred (x:xs) = if (pred x) then x:(filter1 pred xs)
                                  else filter1 pred xs

--------------------------------------------------------------------------------
-- returns list in 2nd argument filtered by predicate in 1st argument
filter2 :: (a -> Bool) -> [a] -> [a]
filter2 pred []  = []
filter2 pred (x:xs)
    | pred x    = x:(filter2 pred xs)
    | otherwise = filter2 pred xs

--------------------------------------------------------------------------------
-- returns list in 2nd argument filtered by predicate in 1st argument
filter3 :: (a -> Bool) -> [a] -> [a]
filter3 pred xs = concat (map (ifp pred) xs)

-- returns either a singleton list containing the second argument, or an empty
--  list, depending on the result of applying the predicate
ifp :: (a -> Bool) -> a -> [a]
ifp pred x
    | pred x    = [x]
    | otherwise = []

--------------------------------------------------------------------------------
-- returns list in 2nd argument filtered by predicate in 1st argument
filter4 :: (a -> Bool) -> [a] -> [a]
filter4 pred xs = [x | x <- xs, pred x] 

--------------------------------------------------------------------------------
-- appends 2 lists, making an appeal to reverse
app1 :: [a] -> [a] -> [a]
app1 xs ys = subapp (reverse xs) ys

-- "backs" first argument onto the second
subapp :: [a] -> [a] -> [a]
subapp [] ys     = ys
subapp (x:xs) ys = subapp xs (x:ys)

--------------------------------------------------------------------------------
-- appends 2 lists without making an appeal to reverse
app2 :: [a] -> [a] -> [a]
app2 [] ys     = ys
app2 (x:xs) ys = x:(app1 xs ys)

--------------------------------------------------------------------------------
-- reverses a list, making an appeal to append
rev1 :: [a] -> [a]
rev1 [] = []
rev1 (x:xs) = (rev1 xs) ++ [x]

--------------------------------------------------------------------------------
-- reverses a list without making an appeal to append
rev2 :: [a] -> [a]
rev2 xs = revacc xs []

-- accumulating list reversal
revacc :: [a] -> [a] -> [a]
revacc [] ys     = ys
revacc (x:xs) ys = revacc xs (x:ys)

--------------------------------------------------------------------------------
-- transposes a matrix
transpose :: [[a]] -> [[a]]
transpose ([]:_) = []
transpose rs     = (map head rs):(transpose (map tail rs))

--------------------------------------------------------------------------------
-- returns a list containing all results from the imperative algorithm:
--  for (x = 1; x <= 10; x++) {
--      for (y = x; y <= 10; y++) {
--          for (z = y; z >= x; z--) {
--              foo( z );
--          }
--      }
--  }
looper :: (Int -> a) -> [a]
looper foo = [foo z | x <- [1..10], y <- [x..10], z <- (reverse [x..y])]

--------------------------------------------------------------------------------
-- returns a list of all permutations of the input list
perm :: (Eq a) => [a] -> [[a]]
perm [] = [[]]
perm as = [a:b | a <- as, b <- perm (remove a as)]

-- removes all occurence of an element from a list
remove :: (Eq a) => a -> [a] -> [a]
remove a lst = filter (/= a) lst

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