Brandon.Si(mmons)

code / art / projects

Making Your Zipper Disappear With Zippo

I’ve finally had a chance to look at how my new lens-based, power-packed, minimal zipper library zippo looks when compiled, and initial results are pleasing!

For example, here is a silly zipper operation that increments the nodes of a sort-of tree:

module Main where

import Control.Category((>>>))
import Data.Lens.Zipper
import Data.Yall.Lens

data Tree a = Br { _lBranch :: NodeBr a
                 , _rBranch :: NodeBr a }
            deriving Show

data NodeBr a = NodeBr { _node :: a }
    deriving Show

-- START BOILERPLATE
lBranch = lens _lBranch (\(Br _ r) l-> Br l r)
rBranch = lens _rBranch (\(Br l _) r-> Br l r)
node = lens _node $ const NodeBr
-- END BOILERPLATE

-- example data:
t = Br (NodeBr 1 ) (NodeBr 3 )

-- zipper operations
incNode = moveP node >>> modf (+1) >>> moveUp
zops = zipper >>> moveP lBranch >>> incNode >>> moveUp >>> 
        moveP rBranch >>> incNode >>> close

main = print $ zops t

When compiled with

ghc --make -fforce-recomp -ddump-simpl -dsuppress-all -O2 SimpleExample.hs

this produces the following beautiful core:

zops =
  \ w_s2uY ->
    case w_s2uY of _ { Br ww_s2v0 ww1_s2v1 ->
    Br
      (NodeBr
         (case ww_s2v0 of _ { NodeBr ds_d16N ->
          plusInteger ds_d16N incNode2
          }))
      (NodeBr
         (case ww1_s2v1 of _ { NodeBr ds_d16N ->
          plusInteger ds_d16N incNode2
          }))
    }

Alakazam! Some more complex examples also produced nice code with performance identical to the most straightforward equivalent definition.

TODOs

The above gave me an opportunity to test a handful of rewrite rules which I’m excited about, but first I need to tie up some loose ends to get this useful:

  1. create some combinators that together with (>>>) form a nice DSL for zipper operations, including nice support for partial lens “Alternative-like” statements
  2. get the underlying lens library situation sorted out:
    • either add automatic lens deriving TH to yall (not looking forward to this), or…
    • see if I can convince ekmett to modify lens in some clever way to support my use case (not optimistic about this)
    • use data-lens now that it does “partial lenses”
  3. look at some of Oleg’s zipper stuff for actual applications of zippers to guide development

Leave a note if you have questions or ideas for me.

Comments