To: springer@cs.indiana.edu
In-reply-to: "George Springer"'s message of Tue, 10 Nov 1992 11:33:21 -0500 <9211101633.AA09126@bambam.cs.iastate.edu>
Subject: Some more suggestions for Springer & Friedman book
--text follows this line--
George,
	Ok, although I do think the deep-recur in 7.5 is the more sophisticated
model, for the following reason.  The inductive definition of a tree is

  DEFINITION	    	STANDARD FORM of proc
a tree of alpha 	(LAMBDA (tree)
is either:        	  (COND
   '()             	    [(null? tree) ...]
or (cons t1 t2)    	    [(pair? (car tree))...]
or (cons d t1)     	    [ELSE ...]))
where t1, t2 are trees of alpha
  and d is an alpha

I'm not hiding any of the type theory here.  In the type tree of alpha,
alpha is a type variable; for example, you can have a tree of number
or tree of boolean, where the atomic elements of the tree are numbers
or booleans (respectively).
What I learned from section 7.5, to my surprise, was that the test
	(pair? tree)
does not really distinguish case 2 (cons t1 t2) from case 3 (cons d t1),
because t1 can be either a pair (cons ...) or the empty list ().
So in some sense your program in 7.5 corresponds more closely to what one
would have to write in a typed language such as standard ML...

datatype
    'a tree = nil 
  | cons of 'a treeOrData * 'a tree
and 
    'a treeOrData = left of 'a tree 
  | leaf of 'a;

val deepRecur =
    fn (seed, itemProc, listProc) =>
    let val rec helper =
	fn (nil) => seed
	 | cons(left(t1), t2) => listProc(helper(t1), helper(t2))
	 | cons(leaf(a), t2) => itemProc(a, helper(t2))
    in
	helper
    end;

where deepRecur has type
	 'a * ('b * 'a -> 'a) * ('a * 'a -> 'a) -> 'b tree -> 'a
for all 'a and 'b.  ('a is the type of seed, itemProc has type 'b*'a->'a, etc.)

This description corresponds to section 7.5, not 4.3 and 4.4.