does this have a name (recusive datatypes)
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
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
[Lots of very useful information snipped...]
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)
Well, you could say:
ltree2s (Leaf a) = S a (Pair (Nil,Nil)) ltree2s (Fork l r) = S undefined (Pair (ltree2s l, ltree2s r))
and
s2ltree (S a (Pair (Nil,Nil))) = Leaf a s2ltree (S _ (Pair (l,r))) = Fork (s2ltree l) (s2ltree r)
so perhaps not exactly isomorphic, since there are two different strees which get mapped to the same ltree, but "pretty close" (at least we have a homomorphism in one direction). but really, thanks for the pointers...i'll get reading :) - Hal
On Wednesday 10 April 2002 11:07 am, Hal Daume III wrote:
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) probably more...
It seems to me that this is very similar to the "Mu" datatype from Mark Jones' paper "Functional Programming with Overloading and Higher-Order Polymorphism" (http://www.cse.ogi.edu/~mpj/pubs.html) He has examples of isomorphisms with lists and rose trees, etc. Here is an example: data Mu f = In (f (Mu f)) type IntList = Mu IntListF data IntListF a = Nil | Cons Int a nil = In Nil cons x xs = In (Cons x xs)
Is there any theory about what types of recursive data structures can be captured with "S" and what types cannot? It seems that those
The paper also mentions some stuff about anamorphisms and catamorphisms, which are apparently like generalized folds and unfolds, which you might be interested in. (I don't pretend to be an expert as I have just found out about them myself.)
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
Here is my attempt at a Show instance for S s (It works, but I'm not sure how to get rid of all the escaped quote marks): data S s a = Nil | S a (s (S s a)) newtype Id a = Id a instance Functor Id where fmap f (Id i) = Id (f i) instance Show a => Show (Id a) where show (Id a) = show a instance Functor s => Functor (S s) where fmap f Nil = Nil fmap f (S a ss) = S (f a) (fmap (fmap f) ss) instance (Functor s, Show a, Show (s String)) => Show (S s a) where show Nil = "Nil" show (S a ss) = show a ++ show (fmap show ss) infixr 5 `cons` cons x xs = S x (Id xs) test :: S Id Int test = 1 `cons` 2 `cons` 3 `cons` Nil main = print test -- 1"2\"3\\\"Nil\\\"\""
participants (3)
-
Brian Huffman -
Hal Daume III -
Ralf Hinze