Gentle tutorial on zippers Let's say that we'd like to simulate the url history traversal in a web browser. That is, we'd like to model how a web browser handles the forward and back button behavior and how it affects what the user sees on the location bar. Concretely, if we visit the following sequence of pages: 1. http://lambda-the-ultimate.org/ 2. http://plt-scheme.org/ 3. http://caml.inria.fr/ then our browser location bar will show the third url. Pressing the "Back" button repeatedly brings us to the second and first urls, and pressing forward brings back toward the third. To be more formal about this, we'll say that an *url* will be a string, and that an *urllist* will be either: 1. empty, or 2. (cons u r) where *u* is an url and *r* an urllist. A concrete instance of an *urllist* is: (cons "http://lambda-the-ultimate.org/" (cons "http://plt-scheme.org/" (cons "http://caml.inria.fr/" empty))) We'll also like to model our current position within this urllist with a separate structure called a *location*, which will include a urllist. We can imagine that the location acts as an arrow pointing at the url that we're currently on. Here's our first (incomplete!) shot at capturing this idea. A *location* is going to be a: (make-location u) where *u* will be an urllist. We can define this structure: (define-struct location (urls)) For instance, here's one concrete location: (define my-location (make-location (cons "http://lambda-the-ultimate.org/" (cons "http://plt-scheme.org/" (cons "http://caml.inria.fr/" empty))))) which represents what happens when we visit those three urls in sequence, and then press our back button two times. Our location will be at "http://lambda-the-ultimate.org", and we expect pressing the forward button at this state to relocate ourselves to the plt-scheme.org web site. Oh, before we forget, let's write the accessor to get the url that shows up on the location bar: ;; location-url: location -> (union url #f) ;; Returns the url at our current location. If our history is ;; empty, returns #f. (define (location-url a-location) (cond [(empty? (location-urls a-location)) #f] [else (first (location-urls a-location))])) Given these definitions, there are two natural functions we'd like to have: we'd like to have go-forward and go-backward to move us through our history. Let's try to tackle go-forward, since that seems relatively straightforward. ;; go-forward: location -> (union location #f) ;; Moves us forward in browser history. If we are at the ;; end of the history, returns #f. (define (go-forward a-location) (cond [(empty? (location-urls a-location)) #f] [else (make-location (rest (location-urls a-location)))])) So this is fairly simple so far. But we're about to hit a snag: how do we model go-backward? Let's imagine the following setup: (define a-loc (make-location (cons "a" (cons "b" empty)))) If we try to do: (location-url (go-backward (go-forward a-loc))) ==> (location-url (go-backward (go-forward (make-location (cons "a" (cons "b" empty)))))) ==> (location-url (go-backward (make-location (cons "b" empty)))) The problem is that, when we move forward, we lose the information we need to go back. Like the story of Hansel and Gretel, we find taking one step forward into the forest and getting lost. We don't remember enough information to get us back home. What did Hansel and Gretel do in this situation? 'When it was noon, Gretel shared her piece of bread with Hansel, who had scattered his by the way. Then they fell asleep and evening passed, but no one came to the poor children. They did not awake until it was dark night, and Hansel comforted his little sister and said: "Just wait, Gretel, until the moon rises, and then we shall see the crumbs of bread which I have strewn about, they will show us our way home again."' --- http://www.mordent.com/folktales/grimms/hng/hng.html Those clever kids. Let's do the same thing. Let's say that a *trail* is either: 1. empty, or 2. (cons u t) where u is a url and t is a trail. The idea is to maintain a breadcrumb trail behind us as we move forward from one location to another; by doing so, we'll have enough information to get back to where we started. Let's first revise our location data definition: A *location* is going to be a: (make-location u t) where u will be an urllist and t will be a trail. Concretely, when we start off, we have no crumbs trailing behind us: (define my-location (make-location (cons "http://lambda-the-ultimate.org/" (cons "http://plt-scheme.org/" (cons "http://caml.inria.fr/" empty))) empty)) When we move forward, we toss a url crumb behind us: ;; go-forward: location -> (union location #f) ;; Moves us forward in browser history. If we are at the ;; end of the history, returns #f. (define (go-forward a-location) (cond [(empty? (location-urls a-location)) #f] [else (make-location (rest (location-urls a-location)) (cons (first (location-urls a-location)) (location-trail a-location)))])) And now that we have that trail, we have enough context that we can go backward: ;; go-backward: location -> (union location #f) ;; Moves us backward in browser history. If we are at the ;; beginning of the history, returns #f. (define (go-backward a-location) (cond [(empty? (location-trail a-location)) #f] [else (make-location (cons (first (location-trail a-location)) (location-urls a-location)) (rest (location-trail a-location)))])) Hurrah! In fact, not only can we simulate going backward and forward, but we can visit pages too: ;; visit: url location -> location ;; Moves to another url, replacing our forward history. (define (visit a-url a-location) (cond [(empty? (location-urls a-location)) (make-location (cons a-url empty) empty)] [else (make-location (cons a-url empty) (cons (first (location-urls a-location)) (location-trail a-location)))])) Let's see this in action: ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; > (location-url (go-backward (visit "http://caml.inria.fr/" (visit "http://plt-scheme.org" (visit "http://lambda-the-ultimate.org" (make-location empty empty)))))) "http://plt-scheme.org" > (location-url (go-backward (go-backward (visit "http://caml.inria.fr/" (visit "http://plt-scheme.org" (visit "http://lambda-the-ultimate.org" (make-location empty empty))))))) "http://lambda-the-ultimate.org" > (location-url (go-forward (go-forward (go-backward (go-backward (visit "http://caml.inria.fr/" (visit "http://plt-scheme.org" (visit "http://lambda-the-ultimate.org" (make-location empty empty))))))))) "http://caml.inria.fr/" ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; So in summary, we can do in-place local edits of our list of urls. The location and trail structures that we've been using to keep context --- the knowledge of how to get back home --- is a specific instance of what's known as a "zipper". The paper "The Zipper", by Gerard Huet, gives a faster introduction to them, and I highly recommend the paper. I hope this helps! References ---------- Gerard Huet: Functional Pearl / The Zipper. J. Functional Programming 7(5): 549-554, September 1997.