{-
   Title: Examples from the second lecture
   Author: Robin Cockett
   Date: 14 Jan 2003

   Notes: some of these functions are in the standard prelude can 
          you identify them?
-}

-- folding over a list (recall this replaces constructors 
-- by functions) allows one to abstract many programs

foldlist::(a -> b -> b) -> b -> [a] -> b
foldlist f_cons f_nil [] = f_nil
foldlist f_cons f_nil (x:xs) = f_cons x (foldlist f_cons f_nil xs)

-- Now we can define a number of functions using this pattern of 
-- computation.

-- Flatten a list of lists into a list
flatten:: [[a]] -> [a]
flatten = foldlist (++) [] 

-- Notice the syntactic technique of turning an infix operaor into a function
-- by enclosing it in parentheses.

-- Sum a list of integers
sumlist:: [Integer] -> Integer
sumlist = foldlist (+) 0

{-  Here is the mental picture of the computation which takes a  
    list and turns it into an expression which can be evaluated

             :                            +
            / \                          / \
           /   \                        /   \
          3     :            ===>      3     +
               / \                          / \
              /   \                        /   \
             7    []                      7     0
 -}

-- Multiply a list of integers
multlist:: [Integer] -> Integer
multlist = foldlist (*) 1

--The disjunction of a list of booleans
orlist:: [Bool] -> Bool
orlist = foldlist (||) False

--The conjunction of a list of booleans
andlist::[Bool] -> Bool
andlist= foldlist (&&) True


-- lists are all very well but the real value of functional languages is that 
-- they give support for complex datatypes.  Let us consider binary trees:

data Tree a = Tip a
            | Node (Tree a) (Tree a)
     deriving (Show,Eq)

-- the CONSTRUCTORS are Tip and Node: in this tree all information is carried 
-- by the leaves.

-- Here is a function which takes a binary tree and returns the list of its 
-- leaves.

leaves:: Tree a -> [a]
leaves (Tip a) = [a]
leaves (Node t1 t2) = (leaves t1)++(leaves t2)

-- (Note: this is NOT an efficient function: it is O(n^2).  Can you see why ..
--  can you see how to write the function to make it O(n)?

-- Here is a function which takes a binary tree and returns the sum of its 
-- leaves.

sumtree:: Tree Integer -> Integer
sumtree (Tip n) = n
sumtree (Node t1 t2) = (sumtree t1) + (sumtree t2)

-- As before we may write an abstraction of these functions which is the 
-- fold function over trees:

foldtree f_node f_tip (Tip x) = f_tip x
foldtree f_node f_tip (Node t1 t2) = f_node (foldtree f_node f_tip t1) 
                                            (foldtree f_node f_tip t2)

-- We may now write abstracted versions of the functions above 

leaves1:: Tree a -> [a]
leaves1 = foldtree (++) (\x -> [x]) 

-- Note here the use of an "anonymous function" (\x -> x)  which actually does 
-- nothing except to pass its argument back.

sumtree1:: Tree Integer -> Integer
sumtree1 = foldtree (+) (\x -> x)

-- And functions for taking the conjunction and disjunction of the leaves
ortree:: Tree Bool -> Bool
ortree = foldtree (||) (\x ->x)

andtree::Tree Bool -> Bool
andtree = foldtree (&&) (\x->x)

-- We can also write a maptree function which leaves the structure of the 
-- tree the same but maps the leaves according to some function:

maptree:: (a -> b) -> (Tree a) -> (Tree b)
maptree f (Tip x) =  Tip (f x)
maptree f (Node t1 t2) = Node (maptree f t1) (maptree f t2)

-- If we wish to add a number to each leaf in a tree we may now write
incleaves:: Integer -> (Tree Integer) -> (Tree Integer)
incleaves n = maptree (\m -> m+n)

-- trees which hold information at their leaves are all very well but the 
-- these are probably not the sort of trees with which most programmers 
---are familiar.  More common are the trees which hold information at their 
-- leaves: these are the binary search trees:

data STree a = STip 
             | SNode (STree a) a (STree a)
     deriving (Show,Eq)

-- the CONSTRUCTORS are STip and SNode: in this tree all information is 
-- carried in the nodes.

-- Here is a function which takes a binary search tree and returns the 
-- list of its leaves.

sleaves:: STree a -> [a]
sleaves (STip) = []
sleaves (SNode t1 x t2) = (sleaves t1)++[x]++(sleaves t2)

-- (Note: this is NOT an efficient function! Can you see how to make it O(n)?)

-- For any (inductive) datatype one can write a fold function.  Here is the 
-- fold function for STree a:

foldstree:: (b -> a -> b -> b) -> b  -> (STree a) -> b
foldstree f_snode f_stip (STip) = f_stip
foldstree f_snode f_stip (SNode t1 x t2) 
                 = f_snode (foldstree f_snode f_stip t1) x 
                           (foldstree f_snode f_stip t2)

-- For any (inductive) datatype one can write a map function.  Here is the 
-- map function for STree a:

mapstree:: (a -> b) -> (STree a) -> (STree b)
mapstree f STip = STip
mapstree f (SNode t1 x t2) = SNode (mapstree f t1) (f x) (mapstree f t2)


-- Here is how to insert an element into a search tree
insert:: Ord a => a -> (STree a) -> (STree a)
insert a (STip) = SNode STip a STip
insert a (SNode t1 b t2) 
       | a < b = SNode (insert a t1) b t2
       | a > b = SNode t1 b (insert a t2)
       | otherwise = (SNode t1 b t2)

-- Note the use of the guard syntax here!