cl-zipper is a Common Lisp implementation of the Zipper data structure first described by Gerárd Huet.
The code was tested and runs successfuly on each of the following Common Lisp platforms:
First, make sure that you have ASDF installed and loaded:
> (asdf:asdf-version) "2.017"
A simple way to get ASDF is via QuickLisp, which is a library manager for Common Lisp.
At this moment the package is not yet available for download through QuickLisp.
However, it could be installed rather easily by cloning the project
~/quicklisp/local-projects directory and running
(ql:quickload :cl-zipper) in the REPL.
First, start a REPL and load the system:
(asdf:load-system :cl-zipper) (use-package :cl-zipper)
Suppose we have the tree
(a + b) * (c - d) to play with:
(defparameter *loc* (zipper '(* (+ a b) (- c d))))
Now, let's examine the four basic zipper operations:
(go-left loc), and
Every zipper operation gets what we call a loc, or location, which consists in the current focus of attention within the tree, and the return value is a loc that represents the new location after such operation is performed.
For instance, let's take a look at what
(go-down loc) does:
> (documentation 'go-down 'function) "Returns the loc of the leftmost child of the node at this loc, or nil if no children."
Obtaining more information about the current loc and its surroundings:
(defparameter *loc-down* (go-down *loc*)) (car *loc-down*) ;; * (lefts *loc-down*) ;; NIL (rights *loc-down*) ;; ((+ A B) (- C D))
The nice thing about this kind of abstraction is that you can navigate a tree by chaining calls:
(defparameter *loc-down-right* (go-right *loc-down*)) (car *loc-down-right*) ;; (+ A B) (lefts *loc-down-right*) ;; (*) (rights *loc-down-right*) ;; ((- C D))
By now you probably have guessed what the other basic navigation primitives do:
> (documentation 'go-left 'function) "Returns the loc of the left sibling of the node at this loc, or nil."
To zip up to the parent node of a nested loc:
(car (go-up *loc-down-right*)) ;; (* (+ A B) (- C D))
(go-next loc) if you just want to visit the nodes of
the tree in depth-first order:
(defparameter *loc-next-2* (go-next (go-next *loc*))) (car *loc-next-2*) ;; (+ A B) (lefts *loc-next-2*) ;; (*) (rights *loc-next-2*) ;; (- C D)
(go-prev loc) to walk to the opposite direction:
(defparameter *loc-next* (go-prev *loc-next-2*)) (car *loc-next*) ;; * (lefts *loc-next*) ;; NIL (rights *loc-next*) ;; ((+ A B) (- C D))
Now, suppose you have a loc that points to
(defparameter *loc-a* (go-right (go-down (go-right (go-down *loc*))))) (car *loc-a*) ;; A (lefts *loc-a*) ;; (+) (rights *loc-a*) ;; (B)
You can get the leftmost or rightmost loc with a simple function call:
(car (leftmost *loc-a*)) ;; + (car (rightmost *loc-a*)) ;; B
(remove-node loc) to remove the node at loc:
(root-node (remove-node *loc-a*)) ;; (* (+ B) (- C D))
The first functions we'll see are
(insert-left loc node) and
(insert-right loc node):
(root-node (insert-left *loc-a* 'x)) ;; (* (+ X A B) (- C D)) (root-node (insert-right *loc-a* 'x)) ;; (* (+ A X B) (- C D))
If the node at loc is the root of a subtree, it's possible to
insert child nodes with
(append-down loc node) and
(insert-down loc node).
(append-down loc node) function inserts a node as the rightmost
child of the node at loc:
(defparameter *loc-subtree* (go-right (go-down *loc*))) (root-node (append-down *loc-subtree* '(/ x y))) ;; (* (+ A B (/ X Y)) (- C D))
(insert-down loc node) to insert a node as the leftmost child:
(root-node (insert-down *loc-subtree* '(/ x y))) ;; (* ((/ X Y) + A B) (- C D))
(change-node loc node) in order to replace the node at loc:
(root-node (change-node *loc-a* 'x)) ;; (* (+ X B) (- C D))
If the change is modeled by a function, the function
(edit-node loc func &rest args) replaces the node at loc with the
result of applying
(func (car loc) arg1 arg2 ... argN):
(defun crazy-fn (node n1 n2) (if (equal node 'A) n1 n2)) (root-node (edit-node *loc-a* #'crazy-fn 1 2)) ;; (* (+ 1 B) (- C D))
Zippers Are Functional
With zippers you can write code that looks like an imperative,
destructive walk through a tree, call
(root-node loc) when you are
done and get a new tree reflecting all the changes, when in fact nothing
at all is mutated - it's all thread safe and shareable.
If you found bugs or want to add new features to cl-zipper, the first step is to write tests that cover your changes.
As you'll see in a moment, 5am testing framework is required in order to run the tests.
Now, clone this repository and open Lisp REPL at its root directory:
> (ql:quickload :fiveam) ... (:FIVEAM) > (asdf:test-system :cl-zipper) ... T
Copyright (C) Daniel Fernandes Martins
Distributed under the New BSD License. See COPYING for further details.