Re: does this have a name (recusive datatypes)

[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