Zippers for Racket

7.7

top ← prev up next →

Zippers for Racket

David Christiansen

package: zippers

A "zipper" is a cursor into an immutable datatype that supports efficient updates in the immediate vicinity of the focus of the cursor, and where moving the cursor elsewhere takes time and allocation linear in the distance moved.

1 Guide

1.1 Implementing Zippers for New Types

2 Reference

2.1 Zippers

2.2 Context Frames

2.3 Zippers for Pairs

2.4 Zippers for Proper Lists

2.5 Zippers for Immutable Sets

Bibliography

1 Guide

Huet’s Zipper (Huet 1997) is based on splitting a datatype into a focused substructure and the one-hole context within which the focused substructure was found. Contexts are represented as reversed lists, each element of which is analogous to a stack frame if the focus had been found by a series of recursive calls.

The zippers library provides:

A general-purpose zipper abstraction
Struct properties for zipper context frames
Automated generation of context frames for structs

Zippers are represented using the struct zipper. These zippers can traverse tree structures made up of structs (or any other value for which the appropriate frame structures are defined — see prop:zipper-frame for details). Each type of object that occurs in the tree structure can provide a means of refocusing the zipper on one of its child nodes. The refocusing procedures for car and cdr are provided with this library as down/car and down/cdr. Additionally, the focus can be moved upwards to the parent node using up.

1.1 Implementing Zippers for New Types

If your datatype is a tree in which the nodes are structs, then you can use define-struct-zipper-frames to generate the necessary code for instances of that struct to participate in zippers. If your datatype is not a struct, the you need to do a bit more work:

Define frame structs for each direction of descent. Each frame struct type must have the prop:zipper-frame property with an appropriate hole-filling procedure.
Define descent procedures that place the appropriate frame onto a zipper’s context stack, extracting the relevant substructure to the focus. These procedures should raise an exception if they are applied to something other than a zipper focused on the right kind of value. Consider putting the descent procedure into a zipper-movement to enable more checks.
Optionally define other movements, such as left/list and right/list.

2 Reference

2.1 Zippers

struct
(struct zipper (focus context))
focus : any/c
context : (list-of zipper-frame?)

A zipper consists of a focus and a context. The context is a list of frames, each of which can reconstruct one level of the original tree structure. The frame representing the top of the tree is at the end of the list.

Because it must be possible to reconstruct the original tree, the frames must be instances of a struct type with property prop:zipper-frame.

procedure
(zip focus) → zipper?
focus : any/c

Creates a zipper with the identity context and the provided value at the focus.

Examples:

> (zip (list 1 2 3))
(zipper '(1 2 3) '())
> (zip '(set (list 1 2) (list 2 3)))
(zipper '(set (list 1 2) (list 2 3)) '())

procedure
(edit f z) → zipper?
f : (-> any/c any/c)
z : zipper?

Returns a new zipper in which the focused value has been replaced by the result of applying f to the previous focused value.

Example:

> (edit add1
(zip 1))
(zipper 2 '())

struct
(struct zipper-movement (move possible?))
move : (-> zipper? zipper?)
possible? : (-> zipper? boolean?)

A structure representing a zipper movement. A zipper movement consists of two procedures: one that implements the movement, and a predicate that recognizes zippers within which the movement is possible. zipper-movement implements the prop:procedure type property in such a manner as to apply the move procedure, which means that movements can be applied.

See can-move? for a friendly way to recognize whether a zipper-movement? can be applied.

All of the movements exported by this package as well as all of those generated by define-struct-zipper-frames satsify zipper-movement?.

procedure
(can-move? move z) → boolean?
move : zipper-movement?
z : zipper?

Recognizes whether the movement move is applicable to the zipper z by applying its recognizer procedure.

procedure
(up z) → zipper?
z : zipper-not-at-top?

Moves the focus of the z one level upward, "popping" the context stack.

Examples:

> (define sandwich (zip '(bread peanut-butter jam)))
> sandwich
(zipper '(bread peanut-butter jam) '())
> (define fillings (down/cdr sandwich))
> fillings
(zipper '(peanut-butter jam) (list (pair-cdr-frame 'bread)))
> (up fillings)
(zipper '(bread peanut-butter jam) '())

procedure
(rebuild z) → any/c
z : zipper?

Reconstructs the value represented by the zipper z.

Examples:

> fillings
(zipper '(peanut-butter jam) (list (pair-cdr-frame 'bread)))
> (rebuild fillings)
'(bread peanut-butter jam)
> (rebuild (edit reverse fillings))
'(bread jam peanut-butter)

procedure
(zipper-at-top? z) → boolean?
z : any/c

Returns #t if z is a zipper with the identity context, or #f if it is any other value.

Examples:

> sandwich
(zipper '(bread peanut-butter jam) '())
> fillings
(zipper '(peanut-butter jam) (list (pair-cdr-frame 'bread)))
> (zipper-at-top? fillings)
#f
> (zipper-at-top? sandwich)
#t
> (zipper-at-top? 'not-a-zipper)
#f

procedure
(zipper-not-at-top? z) → boolean?
z : any/c

Returns #t if z is a zipper with a non-identity context, or #f if it is any other value.

Examples:

> sandwich
(zipper '(bread peanut-butter jam) '())
> fillings
(zipper '(peanut-butter jam) (list (pair-cdr-frame 'bread)))
> (zipper-not-at-top? fillings)
#t
> (zipper-not-at-top? sandwich)
#f
> (zipper-not-at-top? 'not-a-zipper)
#f

procedure
(zipper-of/c c) → contract?
c : contract?

Takes a contract c and returns a new contract that accepts zippers focused on values accepted by c.

procedure
(zipper-in/c c) → contract?
c : contract?

Takes a contract c and returns a new contract that accepts zippers whose top-level context frame is accepted by by c.

2.2 Context Frames

value
prop:zipper-frame : struct-type-property?

Zipper frames are structs that have an associated method for reconstructing the layer of the original tree that they represent. The structure type property prop:zipper-frame should be set to a two argument procedure that, when called with the struct value that represents a frame and the old focus, returns the tree node.

procedure
(zipper-frame? obj) → boolean?
obj : any/c

Returns #t if obj is an instance of a structure type with property prop:zipper-frame, or #f otherwise.

syntax
(define-struct-zipper-frames [struct-name ...])

struct-name : identifier?

Automatically derives all of the infrastructure necessary for the structures named by struct-name ... to participate in zippers.

In particular, for each accessor named acc associated with each of the structs named in struct-name ..., a struct acc-frame is generated that has every field of struct-name except the one accessed by acc. The prop:zipper-frame structure type property will reconstruct the original instance, with the former focus replacing the field accessed by acc. Additionally, a zipper movement down/acc is generated to descend a zipper along that accessor.

This is an instance of the product rule (McBride 2001) when we construe a datatype as being the fixed point of a coproduct of functors given by structs.

Examples:

> (struct branch (left value right) #:transparent)
> (struct leaf () #:transparent)
> (define-struct-zipper-frames branch leaf)
> (define a-tree (zip (branch (branch (leaf) 12 (leaf)) 15 (leaf))))
> (zipper-focus a-tree)
(branch (branch (leaf) 12 (leaf)) 15 (leaf))
> (define left-subtree (down/branch-left a-tree))
> (zipper-focus left-subtree)
(branch (leaf) 12 (leaf))
> (define with-new-left-subtree
    (edit (match-lambda
             [(branch l v r) (branch l (* v v) r)])
          left-subtree))
> (rebuild with-new-left-subtree)
(branch (branch (leaf) 144 (leaf)) 15 (leaf))

syntax
(struct-zipper-out [struct-name ...])

struct-name : identifier?

A provide transformer that exports the identifiers that are generated using define-struct-zipper-frames.

2.3 Zippers for Pairs

struct
(struct pair-car-frame (cdr))
cdr : any/c

A zipper frame that represents the fact that the previous focus was a pair and the zipper descended into its car.

struct
(struct pair-cdr-frame (car))
car : any/c

A zipper frame that represents the fact that the previous focus was a pair and the zipper descended into its cdr.

procedure
(down/car p) → zipper?
p : (zipper-of/c pair?)

Descend into the car of a focused pair.

procedure
(down/cdr p) → zipper?
p : (zipper-of/c pair?)

Descend into the cdr of a focused pair.

2.4 Zippers for Proper Lists

struct
(struct list-item-frame (to-left to-right))
to-left : list?
to-right : list?

A zipper frame that represents the fact that the previous focus was a proper list and that the elements in to-left were in reverse order to the left of the current focus and the elements in to-right were in their present order to the right of the current focus.

procedure
(down/list-first l) → zipper?
l : (zipper-of/c pair?)

Descend into the first element of a focused list.

procedure
(down/list-ref i) → zipper-movement?
i : exact-nonnegative-integer?

Descend into element i of a focused list.

procedure
(left/list z) → (zipper-in/c list-item-frame?)
z : (zipper-in/c list-item-frame?)

When focused on an element of a list, move the focus to the element immediately to its left.

procedure
(right/list z) → (zipper-in/c list-item-frame?)
z : (zipper-in/c list-item-frame?)

When focused on an element of a list, move the focus to the element immediately to its right.

2.5 Zippers for Immutable Sets

struct
(struct set-member-frame (other-members))
other-members : set?

A zipper frame that represents the fact that the previous focus was a set and the zipper descended into one of its members.

procedure
(down/set-member element) → zipper-movement?
element : any/c

Descend into element in a focused set.

Bibliography

Gérard Huet. Functional Pearl: The Zipper. Journal of Functional Programming 7(5), pp. 549–554, 1997.

Conor McBride. The Derivative of a Regular Type is its Type of One-Hole Contexts. Unpublished, available from author, 2001.

top ← prev up next →