> Does this have a name:
> > data S s a = 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 be
> captured with "S" and what types cannot? It seems that those
> datastructures which are isomorphic to S x for some x (satisfying certain
> 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:
data LTree a = 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 types':
http://www.informatik.uni-bonn.de/~ralf/publications.html#J9
> 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 instance
> declarations) or is it theoretically not possible?
You need higher-order contexts, see Section 7 of the `Derivable
type classes' paper
http://www.informatik.uni-bonn.de/~ralf/publications.html#P13
Cheers, Ralf
_______________________________________________
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
