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