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 | [EMAIL PROTECTED] than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell