Zippers in F#

This image was selected as a picture of the we...

This image was selected as a picture of the week on the Czech Wikipedia for th week, 2007. (Photo credit: Wikipedia)

I recently read the chapter on “zippers” in the great Haskell book Learn You a Haskell for Great Good by Miran Lipovaca, and I decided to implement zippers in F# – you can find my code here.

Zippers are a great way to easily navigate and edit functional, immutable, recursive datastructures.

A zipper is just a pair, consisting of the part of data which has “focus” and a list of “breadcrumbs”. A “breadcrumb” in turn is like a piece of data with a “hole” in it.

Let’s look at the example of a binary tree! When you first create a zipper for it, the focused data is the whole tree, and the list of breadcrumbs is empty.

Now lets say you want to navigate to the left child. Then the left child is in focus, and the list of crumbs contains one crumb, which contains the element at the tree root and its right child subtree, but a “hole” instead of the left child subtree.

If next we want to move to the right child of the left child, this right child (grandchild of the root) will now be in focus, and a second breadcrumb is added. This second breadcrumb now has a hole as its right subtree.

Say we want to replace the focused subtree with another tree. All we have to do is fill the hole in the second breadcrumb with the new subtree, then fill the hole in the first breadcrumb with the result. We end up with a new tree, where the left-right “grandchild subtree” has been replaced.

This idea works for all kinds of recursive data structures. In my code, I implemented it in a general way, then supplied specific implementations for binary trees and lists.

I also demonstrated the use of zippers by giving a demo implementation of the game of Pangolins. The game “database” is a binary tree, with questions at the inner nodes and animal names at the leaves. To play, one starts at the question at the root and then moves down the tree (right or left according to questions being answered by yes or no) until one gets to a leaf, which is then the “best guess” of the animal the player had in mind. If the guess was correct, that’s it. If it was wrong, the player is prompted for the right answer and for a question to distinguish between the wrong guess and the right answer. Then the tree has to be updated, replacing the original leaf with a new subtree containing the new question.

All this is trivially easy with zippers – so have a look at the code and see for yourself!

Pangolins

A sample session with my Pangolins Demo.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: