CMSC 22300
Homework 4, Due 5/7/2012, 11pm

1. [30] Tree search functor, for depth-first and breadth-first search.

  datatype 'a tree = Node of 'a * 'a tree list

  (* search : ('a -> bool) -> 'a tree -> unit *)
  fun search prop tree = 
      let fun try pending =
	      let val (Node(x,children),pending') = get pending
	       in if prop x
	          then (print "found"; ())
		  else try(foldl put pending' children)
	      end
       in try(put(tree,empty))
	  handle EMPTY => (print "failed"; ())
      end

This tree search function depends on a buffer abstraction
that has a type buffer, an empty buffer value, and two operations
put and get that add and remove elements from the buffer. The
get operation on buffers can raise an exception EMPTY when
the argument is the empty buffer.

(a) Define a module signature for the buffer abstraction.

(b) Define a search functor by abstracting the above definitions
over the buffer signature.

(c) Define two argument structures implementing the buffer signature
as FIFO queues and FILO stacks (i.e. lists), and define search
structures by applying the search functor to each of these buffer
structures.  Note that the search structure using queues as buffers
implements breadth-first search of the trees, while the one using
stacks implements depth-first search.

Template file treesearch.sml will be provided.


2.[40] Translation from SML to Haskell versions.
Translate the SML code for the provided solution to the following
homework problems into corresponding Haskell code.

(a) Hw 1.4, simple RPN calculator (file: calculator.hs)
(b) Hw 1.5, simple compiler to RPN (file: compiler.hs)
(c) Hw 2.3, unification (file: unify.hs)
(d) Hw 3.2, equalBase (file: equalbase.hs)

3.[10] Review the SML code for the typechecker in typecheck2.zip,
and identify where translation to Haskell would not be
straightforward.  (file: hw4-3.txt)