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