does this have a name (recusive datatypes)

[Ralf Hinze]

> 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=
e
> captured with "S" and what types cannot?  It seems that those
> datastructures which are isomorphic to S x for some x (satisfying certa=
in
> 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=
s':
=09http://www.informatik.uni-bonn.de/~ralf/publications.html#J9=20

> 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=
nce
> declarations) or is it theoretically not possible?

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

=09http://www.informatik.uni-bonn.de/~ralf/publications.html#P13

Cheers, Ralf