zippo: a lightweight lens-based, type-checked, heterogenous zipper

I finished this new zipper library which you can get with a

cabal install zippo

and fork it on github.

After working for a long time on pez, I wanted to try a zipper library that was also based on lenses, but where heterogenous move up operations would be type-checked, as would a move up past the “top” of the structure.

It looks as though instant-zipper is the only other zipper package that provides that kind of type safety.

Mini walk-through

The pieces that make up our zipper are

data Zipper st b = Zipper { hist  :: st b , viewf :: b }
data (:>) st b c = Snoc (st b) (c -> b) 
data Top a = Top

Which come together in types that might look like, e.g.

z :: Zipper (Top :> Tree a :> Tree a) a

for a zipper perhaps at the leaf element of a child node in some Tree a type. Of course in most cases, no type annotations will be given.

Here are the zipper enter and leave operations:

zipper :: a -> Zipper Top a
zipper = Zipper Top

close :: (Hist st a b)=> Zipper st b -> a
close (Zipper st b) = runHist st b

The close function was the only tricky part, and Daniel Wagner helped me get this version with nice defaulting using type equality annotations from the TypeFamilies extension:

class Hist st a c  where
     runHist :: st c -> (c -> a)
instance a ~ b => Hist Top a b where
     runHist _ = id
instance (Hist st a b) => Hist ((:>) st b) a c where
     runHist (Snoc st' cb) = runHist st' . cb

We provide two functions to “move down” through a type, for partial lenses (used for multiconstructor types) and safe pure lenses:

move :: (Monad m)=> LensM m b c -> Zipper st b -> m (Zipper (st :> b) c)
move l (Zipper st a) = 
    liftM (uncurry $ Zipper . Snoc st . fmap runIdentity) (runLens l a)

moveP :: (b :-> c) -> Zipper st b -> Zipper (st :> b) c
moveP l = runIdentity . move l

And finally a move upward is just runs the stored continuation on the focus:

moveUp :: Zipper (st :> b) c -> Zipper st b
moveUp (Zipper (Snoc st cont) c) = Zipper st $ cont c