does this have a name (recusive datatypes)

[Hal Daume III]

Does this have a name:

> data S s a = Nil | S a (s (S s a))

it seems to capture the essense of many recursive data structures.  With:

> newtype Id a = Id a
> newtype Pair a = Pair (a,a)

we get that:

  lists are isomorphic to S Id
  binary trees are isomorphic to S Pair
  rose trees are isomorphic to S []

probably more...

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.  For instance,

> class Map s where map :: (a -> b) -> s a -> s b
> instance Map Id   where map f (Id i) = Id (f i)
> instance Map Pair where map f (Pair (a,b)) = Pair (f a, f b)
> instance Map []   where map = Prelude.map
> instance Map s => Map (S s) where
>    map f Nil = Nil
>    map f (S a ss) = S (f a) (map f ss)

(note i haven't actually loaded this class stuff in a compiler so i might
have a typo or soemthing, but it should be clear).  it seems the same can
be applied to folds and filters, so certainly if s is a functor, so is S
s, but what more can we say?

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?

 - Hal

--
Hal Daume III

 "Computer science is no more about computers    | hdaume@isi.edu
  than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume