does this have a name (recusive datatypes)

Ralf Hinze
Wed, 10 Apr 2002 20:42:55 +0200

> Does this have a name:
> > data S s a =3D Nil | S a (s (S s a))

I sometimes use the name `generalized rose tree' but that's
certainly not standard. Chris Okasaki uses this data type,
for instance, to implements priority queues with an efficient
merge, see his book `Purely functional data structures'.

> Is there any theory about what types of recursive data structures can b=
> captured with "S" and what types cannot?  It seems that those
> datastructures which are isomorphic to S x for some x (satisfying certa=
> properties) are exactly those on which one can apply things like maps,
> filters and folds.

Not true. Binary leaf trees cannot be captured as `S' always has
a label in the internal nodes:

=09data LTree a =3D Leaf a | Fork (LTree a) (LTree a)

Note that you can define maps for virtually every data type (if we ignore
function spaces), see the paper `Polytypic values possess polykinded type=

> Also, if we want to write a show instance for S s, this seems to be
> impossible.  Is it?  If so, is this a weakness in Haskell (cyclic insta=
> declarations) or is it theoretically not possible?

You need higher-order contexts, see Section 7 of the `Derivable
type classes' paper


Cheers, Ralf