Cristiano Paris wrote: > > I'm trying to catch the connection between delimited continuations and > zippers so I wrote a (kinda) zipper interface to a simple tree > structure. Here's the code: > > ------- > module Main where > > import Data.Maybe > > data Tree a = Leaf a | Fork (Tree a) (Tree a) deriving Show > > tree = Fork (Fork (Leaf 1) (Leaf 2)) (Fork (Leaf 3) (Fork (Leaf 4) (Leaf 5))) > > data ZContext a = ZContext { moveUp :: Maybe (ZContext a), > moveLeft :: Maybe (ZContext a), > moveRight :: Maybe (ZContext a), > this :: Maybe a } > > initZ t = doInitZ Nothing t > where > doInitZ c (Leaf a) = ZContext c Nothing Nothing $ Just a > doInitZ c t@(Fork l r) = ZContext c (Just $ doInitZ s l) > (Just $ doInitZ s r) > Nothing > where s = Just $ doInitZ c t > ------- > > You access the tree in the following way (session from ghci): > > *Main> this $ fromJust . moveLeft $ fromJust . moveLeft $ initZ tree > > I read Haskell book's Chapter about Zippers on Wikibooks and I think I > understood the underlying concept even if the implementation still > seems to me a bit arbitrary (i.e. different implementation can be > provided even if the proposed one is neat thinking of > differentiation). > > Hence, I decided to go experimenting myself and came up with the above > solution. I know that the interface to a tree having values only on > leaves is pointless as the main advantage of using a Zipper is to get > O(1) performance on updating but I wanted to keep it as simple as > possible. > > So, can you provide some comments on that implementation? Thank you > all, as usual!
The unusual thing about your implementation is probably that you're tying a knot by making both moveUp and moveLeft record fields. This reminds me of Weaving a web. Ralf Hinze and Johan Jeuring. 2001. http://www.informatik.uni-bonn.de/~ralf/publications/TheWeb.ps.gz The problem with knot-tying / sharing is of course that they are tricky to update. What about the crucial function update :: ZContext a -> Maybe a -> ZContext a that changes the data at a leaf? I think that with your current approach, you'd have to regenerate the whole context which pretty much defeats the purpose of a zipper. Regards, apfelmus -- http://apfelmus.nfshost.com _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe