{- We LOVE lists (part 2)

     You can do alot with lists!  But they are by no means the end of the story:
     they are just one well-known datatype ...

     All datatypes come with a "map" function and a "fold" function.  
     The fold function (often called "fold left" for lists) is particularly 
     fundamental ...

     These notes begin to explore this aspect of lists ... and end by describing
     list comprehension -- a powerful feature which has leaked into other
     languages

-}

data SF a = SS a | FF
  deriving (Eq,Show)

sfmap:: (a -> b) -> ((SF a) -> (SF b))
sfmap f (SS x) = SS (f x)
sfmap f FF = FF

--mapping a function over a list
mymap:: (a -> b) -> ([a] -> [b])
mymap f [] = []
mymap f (a:as) = (f a):(mymap f as)

--given a list of booleans compute their conjunction
myAND:: [Bool] -> Bool
myAND [] = True
myAND (b:bs) = b && (myAND bs)

--given a list of booleans compute their disjunction
myOR:: [Bool] -> Bool
myOR [] = False
myOR (b:bs) = b || (myOR bs)

-- Checking whether there  is something in the list which satisfies
-- a predicate
inlist:: (a -> Bool) -> [a] -> Bool
inlist pred as = myOR (mymap pred as)

-- mymember again ..
mymember:: Eq a => a  -> [a] -> Bool
mymember a = inlist (\x -> a==x)

-- Is there a number greater than m in the list?
myGT:: Integer -> [Integer] -> Bool
myGT m = inlist (\x -> x>m)

-- Zipping two lists: what happens if they are different lengths?
-- We want the zip to fail!!

myzip:: [a] -> [b] -> SF [(a,b)]
myzip [] [] = SS []
myzip (a:as) (b:bs) =
      case myzip as bs of
         SS xs -> SS ((a,b):xs)
         FF -> FF
myzip _ _ = FF

-- try myzip [1,2,3] "abc"!!  Point is "abc = ['a','b','c']

-- Zipping with two lists and applying a function f

myzipwith:: ((a,b) -> c) -> [a] -> [b] -> (SF [c])
myzipwith f as bs = sfmap (mymap f) (myzip as bs)

-- Currying and uncurrying -- and who was Haskell Curry anyway?
-- we can typs a function in two subtely different ways:
--       f:: a -> b -> c   or   f':: (a,b) -> c
--the first is a "curried" version the second is "uncurried"
-- they are interdefinable
--       f a b = f'(a,b)   and   f'(a,b) = f(a,b)
-- however what we cannot (immediately) do with the second function
-- is to get a function
--              (f a) :: b -> c
-- to do this for f' we have to explicitly "curry" it
--              g a = (\b -> f'(a,b)):: b -> c

-- An important and useful function is "filtering" a list:
-- this removes elements from a list which do not satisfy a
-- predicate ...

myfilter:: (a -> Bool) -> [a] -> [a]
myfilter p [] = []
myfilter p (a:as) = if (p a) then a:(myfilter p as)
                  else myfilter p as

-- Note "if then else" could have been replaced by guards
--        myfilter p (a:as)| p a = a:(myfilter f as)
--                         | otherwise = myfilter f as
-- much nicer!!!

-- Reversing a list:
-- The naive reverse: complexity O(n^2) ... ugh!

n_reverse:: [a] -> [a]
n_reverse [] = []
n_reverse (a:as) = (n_reverse as)++[a]

-- Reversing a list the "fast" way: complexity O(n) .. better!

f_reverse:: [a] -> [a]
f_reverse xs = shunt xs []
   where
      shunt:: [a] -> [a] -> [a]
      shunt [] ys = ys
      shunt (x:xs) ys = shunt xs (x:ys)
      
------------------------------------------------
-- folding on a list (foldr in prelude)
-- here is a more sophisticated but - if you can get
-- your mind round it - very useful higher order
-- function.
-----------------------------------------------

myfold:: (a -> c -> c) -> c -> ([a] -> c)
myfold f c [] = c
myfold f c (x:xs) = f x (myfold f c  xs)


--  adding up a list of integers
myADD:: [Integer] -> Integer
myADD = myfold (+) 0

-- multiplying a list of  integers
myMUL:: [Integer] -> Integer
myMUL = myfold (*) 1

-- appending two list
myAPP:: [a] -> [a] -> [a]
myAPP as bs = myfold (:) bs as

-- flattening a list
myFLATTEN:: [[a]] -> [a]
myFLATTEN = myfold myAPP []

-- another version of map for a list

myfmap:: (a -> b) -> ([a] -> [b])
myfmap f = myfold (\a as -> (f a):as) []

myffilter:: (a -> Bool) -> [a] -> [a]
myffilter p = myfold
                (\a as -> if (p a) then a:as else as)
                []

-- This is a higher-order reverse for you to puzzle over
-- (it will not be on any tests)

myfreverse :: [a] -> [a]
myfreverse as = myfold (\ a f -> (\x -> f(a:x))) id as []

horev:: [a] -> [a] -> [a]
horev = foldr g id where
     g a h x =  h (a:x)


-------------------------------------------
--  List comprehension is powerful
--   ... but can lead to not very
--  efficient code!
-----------------------------------------------


pairs:: [a] -> [b] -> [(a,b)]
pairs as bs = [(a,b) | a <- as, b <- bs]

-- the list comprehension of the above translates out to
-- give (roughly) the following code:

pairs1:: [a] -> [b] -> [(a,b)]
pairs1 as bs = myFLATTEN (mymap (\a -> mymap (\b -> (a,b)) bs) as)

-- the filter function can be written using list comprehension

myfilter1:: (a -> Bool) -> [a] -> [a]
myfilter1 f as = [ a | a <- as, f a]

-- This list coprehension translates out to

myfilter3:: (a -> Bool) -> [a] -> [a]
myfilter3 p as = myFLATTEN (mymap (\a -> if p a then [a] else []) as)

--
-- Here is the translation scheme for list comprehension
--      {[s | a <- t, rest]} = flatten (map (\a -> {[ s | rest]}) t)
--      {[s | p, rest]} = if p then {[s | rest]} else []
--      {[s | ]} = [s]  (rest is empty!)
--
{-  
   Two example of translation:
(1) RHS of pair:
   {[ (a,b) | a <- as, b <- bs ]} 
           = flatten (map (\a -> {[ (a,b)| b <- bs ]}) as )
           = flatten (map (\a -> flatten( map (\b -> {[ (a,b)| ]}) bs)) as)
           = flatten (map (\a -> flatten( map (\b -> [(a,b)]) bs)) as)
(2) of RHS of filter:
   {[ a | a <- as, f a]} 
           = flatten (map (\a -> {[a| f a]}) as)
           = flatten (map (\a -> if (f a) then {[ a | ]} else []) as)
           = flatten (map (\a -> if (f a) then [a] else []) as)                                                
-}




--------------------------------------------------------------
-- Here are four classic examples of using list comprehension
--
-- Quick sort using list comprehension
-- Warning this is not the most efficient quick sort!!
--         ... however, it is pretty elegant!
--

qsort:: (Ord a) => [a] -> [a]
qsort [] = []
qsort (a:as) = (qsort [y|y <- as, y < a])++[a]++(qsort [y|y <- as, y >= a])

--
-- Finding all Pythagorean triples that is (x,y,z) such that x^2 + y^2 = z^2
-- with z =< n
--          ... not very efficient (but elegant)!
--

pythag :: Integer -> [(Integer,Integer,Integer)]
pythag n = [(x,y,z) | z <- [1..n], y <- [1..z], x <- [1..y], x*x+y*y==z*z]

--
-- Finding all prime numbers
-- This implements the sieve of Eratosthenes
--   ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)
--            .. very inefficient but elegant
--

primes:: [Integer]
primes = filterPrime [2..] where
    filterPrime (p:xs) = p:(filterPrime [x|x <- xs, x `mod` p /= 0])

--
--  A Mersenne prime is a prime number that is one less than a power of two.
--  Find all the Mersenne primes ...
--         https://www.mersenne.org/primes/
--  How many can you discover?  May want to speed this up ...
--     (it is not even known whether there are infinitely many!!)
--

mersenne:: [Integer]
mersenne = [ n | n <- primes, mestest n ]  where  
    mestest n = powertwo (n+1)
    powertwo n    | n == 1 = True
                  | n `mod` 2 == 0 = powertwo (n `div` 2)
                  | otherwise = False

--
-- Just crazy!!  Try running this for a week!
--