zipper is:module

A zipper is a structure for walking a value and manipulating it in constant time. This module was inspired by the paper: Michael D. Adams. Scrap Your Zippers: A Generic Zipper for Heterogeneous Types, Workshop on Generic Programming 2010.

This module provides a two-dimensional text zipper data structure. This structure represents a body of text and an editing cursor which can be moved throughout the text, along with a set of editing transformations. Text zippers are generalized over the set of data types that might be used to store lists of characters (e.g., String, Text, etc.). As a result, the most general way to create a text zipper is to use mkZipper and provide all of the functions required to manipulate the underlying text data. Implementations using Text and String are provided.

This module provides a Zipper with fairly strong type checking guarantees. The code here is inspired by Brandon Simmons' zippo package, but uses a different approach to represent the Zipper that makes the whole thing look like his breadcrumb trail, and can move side-to-side through traversals. Some examples types:

• Top :>> a represents a trivial Zipper with its focus at the root.
• Top :>> Tree a :>> a represents a Zipper that starts with a Tree and descends in a single step to values of type a.
• Top :>> Tree a :>> Tree a :>> Tree a represents a Zipper into a Tree with an intermediate bookmarked Tree, focusing in yet another Tree.

Since individual levels of a Zipper are managed by an arbitrary IndexedTraversal, you can move left and right through the IndexedTraversal selecting neighboring elements.

>>> zipper ("hello","world") & downward _1 & fromWithin traverse & focus .~ 'J' & rightmost & focus .~ 'y' & rezip
("Jelly","world")

This is particularly powerful when compiled with plate, uniplate or biplate for walking down into self-similar children in syntax trees and other structures. Given keys in ascending order you can jump directly to a given key with moveTo. When used with traversals for balanced tree-like structures such as an IntMap or Map, searching for a key with moveTo can be done in logarithmic time.

Creation date: Thu Jul 23 08:42:37 2020.

This is an infinite bidirectional zipper

Based on «Scrap Your Zippers: A Generic Zipper for Heterogeneous Types. Michael D. Adams. WGP '10: Proceedings of the 2010 ACM SIGPLAN workshop on Generic programming, 2010» (http://michaeldadams.org/papers/scrap_your_zippers/). Compared to the original syz package, this implementation (based on GTraversable) gives more flexibility as to where a zipper may point to and what is considered as siblings. Specifically, a zipper may point to any element which gtraverse applies its function to.

Example

syz

Consider the classical example: lists. With syz, a list is interpreted as a right-balanced tree.

>>> let z = fromJust . down' $ toZipper ['a'..'d']

>>> getHole z :: Maybe Char
Just 'a'

The zipper z points to the first element of the list. Now let's move to the right:

>>> let z' = fromJust . right $ z

>>> getHole z' :: Maybe Char
Nothing

>>> getHole z' :: Maybe [Char]
Just "bcd"

Instead of pointing to the second element of the list, as one might expect, the zipper z' points to the tail of the list. In order to actually move to the second element, we need another down':

>>> let z'' = fromJust . down' $ z'

>>> getHole z'' :: Maybe Char
Just 'b'

traverse-with-class

GTraversable-based zippers behave more intuitively in this regard, thanks to the uniform instance for lists.

>>> let z = fromJust . down' $ toZipper ['a'..'d'] :: Zipper Typeable [Char]

>>> getHole z :: Maybe Char
Just 'a'

So far it's more or less the same as with syz. We needed to add a type annotation for the zipper itself to clarify the context which should be available at each hole (Typeable in this case). Now let's see what's to the right of us:

>>> let z' = fromJust . right $ z

>>> getHole z' :: Maybe Char
Just 'b'

That is, we jumped right to the second element of the list. Likewise,

>>> let z'' = rightmost z

>>> getHole z'' :: Maybe Char
Just 'd'

So, unlike in syz, all of the list elements are siblings.

Spine-lazy radix tree location manipulation. Allows lookup and successive insertion without retaining the entirety of the key in memory.

Spine-strict radix tree location manipulation. Allows lookup and successive insertion without retaining the entirety of the key in memory.

Zipper over the Data.Tree data structure. This module is based on rosezipper.