does this have a name (recusive datatypes)
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