{- CMSC 22300 Midterm exam
 - Wednesday, Feb 13, 2008
 -}

{- 1.
Define a function 

   interleave :: [a] -> [a] -> [a]

that interleaves two lists. I.e. 

   interleave [1,2,3] [4,5,6,7,8]   ==> [1,4,2,5,3,6,7,8]
-}

{- 2. Use list comprehension to define a function

   addPairs :: [(Int,Int)] -> [Int]

where the result list contains the sums of the elements of
the pairs (m,n), but only where m is less than n. E.g.

   addPairs [(1,2), (3,4), (7,6), (3,5)]  ==>  [3,7,8]
-}

data Tree = Leaf Int | Node Tree Tree

{- 3. fringe of a tree.
Given the type Tree defined above, define a function

   fringe : Tree -> [Int]

that returns the list of Ints at the fringe of the tree,
in left-to-right order. Use the append operation ++.

E.g. 

   fringe (Node (Node (Leaf 3) (Leaf 4))
                (Node (Node (Leaf 1) (Leaf 2)) (Leaf 4)))
   ==> [3,4,1,2,4]
-}

{- 4. incremental fringe function.
Define a second version of fringe that doesn't use the
append function, but instead uses an auxiliary function
that maintains a stack (List) of subtrees to be traversed.
-}

{- 5. Use the IO monad and associated input/output functions
to define a function that inputs two numbers (sequences of
digits) separated by white space and outputs their sum.
-}

{- 6. Explain in detail how to type check the following
function definition:

   f x = if null x then 1 else hd x + 1

Suggestion: use capital letters in the range P .. Z for
type variables.
-}

-- -----------------------------------------------------------
{- Bonus problem.  Define a samefringe function

   samefringe :: Tree -> Tree -> Bool

that returns True if the fringes of the two trees are equal,
but without directly calculating the fringes and comparing
them. I.e. the comparison should be incremental, in the
style of problem 4.
-}