[Haskell-cafe] Re: Zippers

[Heinrich Apfelmus]

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