module Folds where


------------------------------  foldr from the Prelude:

--  foldr            :: (a -> b -> b) -> b -> [a] -> b
--  foldr f z []      = z
--  foldr f z (x:xs)  = f x (foldr f z xs)



------------------------------  foldl from the Prelude:

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

                      -- NOTE:  "f z x" is "flipped"!



------------------------------  defining reverse with accumulation and then foldl

rev0 xs = reva xs []
          where reva []     ys = ys
                reva (x:xs) ys = reva xs (x:ys)             -- start with the accumulator idea (from the "beehive picture")

--             >> <<
rev1 xs = reva [] xs
--                   >>     <<
          where reva ys     [] = ys
                reva ys (x:xs) = reva (x:ys) xs             -- flip reva arguments around
--                   >>     <<         >>    <<
                
rev2 xs = reva [] xs
          where reva ys     [] = ys
                reva ys (x:xs) = reva (flip (:) ys x) xs    -- now flip (:) arguments
                
rev3 xs = reva [] xs
          where reva z      [] = z
                reva z  (x:xs) = reva (flip (:) z x) xs     -- rename ys to z ...
--                      -------------------------------     -- and we get the foldl pattern
                
rev4 xs = reva [] xs
          where reva z = foldl (flip (:)) z                 -- so put in foldl
                
rev5    = reva []
          where reva = foldl (flip (:))                     -- abstract out the xs (above) and the z (below)
                
rev6    = foldl (flip (:)) []                               -- finally, just eliminate the local definition


try rev = rev [1..5]


------------------------------  defining foldl in terms of foldr (!)

foldl' f e l = foldr (\x k e -> k (f e x)) id l e




------------------------------  unfoldr from the List module

unfoldr :: (s -> Maybe (a,s)) -> s -> [a]

unfoldr f s = case f s of
                Nothing    -> []
                Just (a,s') -> a : unfoldr f s'



------------------------------  a Boolean variant of unfoldr

unfold :: (s -> Bool) -> (s -> (a,s)) -> s -> [a]

unfold p f s = if p s then [] else h : unfold p f t
               where (h,t) = f s



------------------------------  two versions of a Boolean unfoldl (we'll use the second)

unfoldl' :: (s -> Bool) -> (s -> (s,a)) -> [a] -> s -> [a]

unfoldl' p f a s = if p s then a else unfoldl' p f (h:a) t
                   where (t,h) = f s

unfoldl :: (s -> Bool) -> (s -> (s,a)) -> s -> [a]

unfoldl p f s = g s []
                where g s a = if p s then a else g t (h:a)
                              where (t,h) = f s