Zipping through it

In my email conversation with Brandon prior to the release of thrist-0.2, I told him that I did not come around implementing reverse thrists, and I showed how they arise naturally when doing computational passes over thrists: (((a, b), c), d) e (f, (g, (h, i))). He asked me whether this has anything to do with zippers, which I answered to the affirmative, my previous ideogram being essentially a thrist zipper. As it maneuvers through the data structure it deconstructs the original thrist, places a new element into focus and zips together a left-associative structure behind. Visually it (kind of) corresponds to the zipper on your jacket.

This post is dedicated to this versatile tool being applied to thrists to obtain an isomorphic data structure which I call the ThristZipper.

As the ideogram demonstrates, this zipper consists of three parts:

1. the left-associate thrist (usually holding the already visited portion),
2. the focus element e,
3. the (right-associative) thrist (usually to be iterated over).

So first we have to define LeftThrist (this is how I prefer to call it).

data LeftThrist :: (* → * → *) → * → * → * where

  LeftNil :: LeftThrist k a a

  LeftCons :: LeftThrist k a b → k b c → LeftThrist k a c

Again, the types match up. Now we can define ThristZipper:

data ThristZipper :: (* → * → *) → * → * → * where

  Focus :: LeftThrist k a b → k b c → Thrist k c d → ThristZipper k a d

It remains to define all the operations on ThristZipper that will make it a versatile tool.

We start with zipInto:

zipInto :: Thrist k a b → Maybe (ThristZipper k a b)

zipInto Nil = Nothing

zipInto (Cons e r) = Just (Focus LeftNil e r)

We can similarly define zipLeftInto, advancing, focus manipulation, maps, folds and getting out on the right or in the left. These are of course left as an exercise to the reader, but I will define retract (the opposite movement from advance) here for good measure:

retract :: ThristZipper k a b → Maybe (ThristZipper k a b)

retract (Focus LeftNil _ _) = Nothing

retract (Focus (LeftCons r e') e t) = Just (Focus r e' (Cons e t))

And a lot prettier in Ωmega (svn HEAD):

retract (Focus []lt _ _) = Nothing

retract (Focus [r; e']lt e t) = Just (Focus r e' [e; t]l)

PS: I definitely plan to make all this part of thrist-1.0 when it arrives.