does this have a name (recusive datatypes)

[Hal Daume III]

[Lots of very useful information snipped...]

> Not true. Binary leaf trees cannot be captured as `S' always has
> a label in the internal nodes:
> 
> 	data LTree a = Leaf a | Fork (LTree a) (LTree a)

Well, you could say:

> ltree2s (Leaf a) = S a (Pair (Nil,Nil))
> ltree2s (Fork l r) = S undefined (Pair (ltree2s l, ltree2s r))

and

> s2ltree (S a (Pair (Nil,Nil))) = Leaf a
> s2ltree (S _ (Pair (l,r))) = Fork (s2ltree l) (s2ltree r)

so perhaps not exactly isomorphic, since there are two different strees
which get mapped to the same ltree, but "pretty close" (at least we have a
homomorphism in one direction).

but really, thanks for the pointers...i'll get reading :)

 - Hal