Trees

[Rustom Mody]

On Thursday, January 22, 2015 at 12:46:22 PM UTC+5:30, Paul Rubin wrote:
> Ian Kelly writes:
> > How do you create a tree containing an even number of elements under
> > this constraint?
> 
> That's a good point, I've usually seen different definitions of trees,
> e.g.
> 
>    data Tree a = Leaf | Branch a (Tree a) (Tree a)
> 
> so a Leaf node doesn't have a value associated with it.

Maybe you should call 'Leaf' instead as EmptyTree 

Then does it answer Ian's question?

Or Nil Null or some such then it is most obviously isomorphic to
the typical way of doing it in C.

The point is that these are frameworks for structural induction.
So choosing base-cases carefully is important.

This may seem harmless but is probably not a good idea

  data Tree a = Empty | Leaf a | Branch a (Tree a) (Tree a)

OTOH the classic S-exp of lisp would be modelled as

 data Sexp b = Cons (Sexp b) (Sexp b) | Leaf b

which captures the fact that the elements (b) are only at the leaves
and the conses provide pure branching without content

ie its not ... Cons b (Sexp b) (Sexp b)...