--
-- lab2.hs
--

-- Sum a list of integers recursively.
sumIntegers1 :: [Integer] -> Integer
-- TODO

-- Sum a list of integers in terms of foldl.
sumIntegers2 :: [Integer] -> Integer
-- TODO

-- Product of a list of integers in terms of foldr.
prodIntegers :: [Integer] -> Integer
-- TODO

-- List append in terms of foldr.
listAppend :: [a] -> [a] -> [a]
-- TODO

-- Insertion sort.
-- This sorts a list of values (which all have to be of type class Ord)
-- according to the following algorithm:
-- 1) Sort the sublist consisting of the tail of the list.
-- 2) Insert the first element (the head) into the sorted sublist at the
--    correct place.
-- Sort the list in ascending order.
insertionSort :: Ord a => [a] -> [a]
-- TODO

-- 'map' that works on two lists.
-- map f a b = [(f a1 b1), (f a2 b2), ...]
--     where a = [a1, a2, ...] and b = [b1, b2, ...]
map2 :: (a -> b -> c) -> [a] -> [b] -> [c]
-- TODO

-- Infinite list of factorials, starting from 0!, using map2.
factorials :: [Integer]
-- TODO

-- Infinite list of prime numbers using list comprehensions and a sieving
-- algorithm. The sieve works as follows: it's n followed by (the sieve of) 
-- all numbers that aren't divisible by n.
primes :: [Integer]
-- TODO

-- Tree data structure.  Note that this is different from the Tree
-- structure used in the lecture.
data Tree a = Leaf | Node a (Tree a) (Tree a)
              deriving Show

-- Sample tree (for testing).
sampleTree :: Tree Integer
sampleTree = Node 1 (Node 2 (Node 3 Leaf Leaf) Leaf) (Node 4 Leaf Leaf)

-- Count the number of leaves in a Tree.
countLeaves :: Show a => Tree a -> Integer
-- TODO

-- Mapping over a tree.
mapTree :: (a -> b) -> Tree a -> Tree b
-- TODO

-- Some data/functions for testing:

-- Counting characters in a String.
countChars :: String -> Integer
countChars = toInteger . length

-- Sample tree of strings.
treeOfStrings :: Tree String
treeOfStrings = Node "foo" 
                (Node "bar" (Node "baz" Leaf Leaf) Leaf) 
                (Node "bam" Leaf Leaf)

treeOfNums :: Tree Integer
treeOfNums = mapTree countChars treeOfStrings


-- Fold on a tree.
foldTree :: (a -> a -> a) -> a -> Tree a -> a
-- TODO

-- Sample use of foldTree: count the characters in a tree of Strings.
charsInTree :: Integer
charsInTree = foldTree (+) 0 (mapTree countChars treeOfStrings)


--
-- end of lab2.hs
--