Hi I've been having a look at zippers over homogenous tree data types, and was wondering how best to represent a heterogeneous graph for manipulation with a zipper.
The main example of zippers I've been looking at is http://okmij.org/ftp/Computation/Continuations.html#zipper-fs and http://okmij.org/ftp/Computation/Continuations.html#zipper from which I've included a small extract at the end of this email to provide extra context if necessary. For contrived example, given a relational model: .Album . |1 . | . | . |1..n 0..n 1 .Performance--------Song . |0..n |1 . | | . | |0..n . |1 WritingCredit . Performer |0..n . ^ ^ | . | |------ | . | | | . | 1 1..n | |1 .Group--------Artist I could write a data type: > data MC > = Album {perfs ::[MC]} > | Performance {album :: MC, song :: MC, performer :: MC} > | Song {perfs :: [MC], artistCredits :: [MC]} > | Group {perfs ::[MC], artists :: [MC]} > | Artist {perfs :: [MC], songCredits :: [MC]} > | Root {albums :: [MC]} The first problem I have with this is that it doesn't enforce enough structural constraints. Secondly, as I understand it, whilst zippers can handle cyclic structures they do so by doing a 'copy-on-write'. I would like to maintain shared instances. I could flatten the data type graph to a minimal spanning tree: > data MCFK = MCFK > data MC > = Album {fKey :: MCFK, perfs ::[MC]} > | Performance {fKey :: MCFK, songFK :: MCFK, performer :: MCFK} > | Song {fKey :: MCFK, artistCredits :: [MCFK]} > | Group {fKey :: MCFK, artists :: [MC]} > | Artist {fKey :: MCFK} > | Root {albums :: [MC], songs :: [MC], groups :: [MC], soloArtists :: [MC]} This seems a bit better. The traversal function doesn't have to worry about cycles and there's less mainenance updates to do. But it still doesn't offer any structural or foreign key guarantees. I thought that I would be able to use a GADT to give structural guarantees, though not FK guarantees, but once I move to a GADT I don't know how to write a traversal function as the next node could be of several different types. Any advice on how to get a safer data structure, and write the necessary traversal function, would be much appreciated. Cheers Daniel Following is an extract from the links above. Note that I have floated the functions local to traverse up to the top level to get at them with GHCi > data Term = Var String | A Term Term | L String Term deriving (Show) > > data Direction = Down | DownRight | Up | Next deriving (Eq, Show) > > traverse :: (Monad m) => (Direction -> Term -> m (Maybe Term, Direction)) -> Term -> m Term > traverse tf term = traverse' tf id Down term >>= maybeM term id > > > traverse' tf next_dir init_dir term = do > (term', direction) <- tf init_dir term > let new_term = maybe term id term' > select tf (next_dir direction) new_term >>= maybeM term' Just > > next next_dir dir = if dir == Next then next_dir else dir > > maybeM onn onj v = return $ maybe onn onj v > > select tf Up t = return Nothing > select tf Next t@(Var _) = return Nothing > select tf dir t@(L v t1) | dir == Next || dir == Down = do > t' <- traverse' tf id Down t1 >>= (return . fmap (L v)) > traverse' tf (next Up) Up (maybe t id t') >>= maybeM t' Just > select tf DownRight t@(A t1 t2) = do > t' <- traverse' tf id DownRight t2 >>= > (return . fmap (\t2'->(A t1 t2'))) > traverse' tf (next Up) Up (maybe t id t') >>= maybeM t' Just > select tf dir t@(A t1 t2) | dir == Next || dir == Down = do > t' <- traverse' tf id Down t1 >>= > (return . fmap (\t1'->(A t1' t2))) > traverse' tf (next DownRight) Up (maybe t id t') >>= > maybeM t' Just > > > --Testing > trav dir term = do print dir; print term; return (Nothing,Next) > > > term1 = A (Var "v1") (L "l1" (A (Var "v2") (Var "v3"))) > > test1 = traverse trav term1 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe