# does this have a name (recusive datatypes)

**Ralf Hinze
**
ralf@informatik.uni-bonn.de

*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=
*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