• Choose a category
• All
• Classic-Fiction

type ListZipper a = ([a], [a])

The first list represents the list that we’re focusing on, and the second list is the list of breadcrumbs. Let’s make functions that go forward and backward in lists:

goForward :: ListZipper a -> ListZipper a

goForward (x:xs, bs) = (xs, x:bs)

goBack :: ListZipper a -> ListZipper a

goBack (xs, b:bs) = (b:xs, bs)

When we’re going forward, we focus on the tail of the current list and leave the head element as a breadcrumb. When we’re moving backward, we take the latest breadcrumb and put it at the beginning of the list. Here are these two functions in action:

ghci> let xs = [1,2,3,4]

ghci> goForward (xs, [])

([2,3,4],[1])

ghci> goForward ([2,3,4], [1])

([3,4],[2,1])

ghci> goForward ([3,4], [2,1])

([4],[3,2,1])

ghci> goBack ([4], [3,2,1])

([3,4],[2,1])

You can see that the breadcrumbs in the case of lists are nothing more than a reversed part of your list. The element that we move away from always goes into the head of the breadcrumbs. Then it’s easy to move back by just taking that element from the head of the breadcrumbs and making it the head of our focus. This also makes it easier to see why we call this a zipper— it really looks like the slider of a zipper moving up and down.

If you were making a text editor, you could use a list of strings to represent the lines of text that are currently opened, and you could then use a zipper so that you know on which line the cursor is currently focused. Using a zipper would also make it easier to insert new lines anywhere in the text or delete existing ones.

A Very Simple Filesystem

To demonstrate how zippers work, let’s use trees to represent a very simple filesystem. Then we can make a zipper for that filesystem, which will allow us to move between folders, just as we do when jumping around a real filesystem.

The average hierarchical filesystem is mostly made up of files and folders. Files are units of data and have names. Folders are used to organize those files and can contain files or other folders. For our simple example, let’s say that an item in a filesystem is either one of these:

A file, which comes with a name and some data

A folder, which has a name and contains other items that are either files or folders themselves

Here’s a data type for this and some type synonyms, so we know what’s what:

type Name = String

type Data = String

data FSItem = File Name Data | Folder Name [FSItem] deriving (Show)

A file comes with two strings, which represent its name and the data it holds. A folder comes with a string that is its name and a list of items. If that list is empty, then we have an empty folder.

Here’s a folder with some files and subfolders (actually what my disk contains right now):

myDisk :: FSItem

myDisk =

Folder "root"

[ File "goat_yelling_like_man.wmv" "baaaaaa"

, File "pope_time.avi" "god bless"

, Folder "pics"

[ File "ape_throwing_up.jpg" "bleargh"

, File "watermelon_smash.gif" "smash!!"

, File "skull_man(scary).bmp" "Yikes!"

]

, File "dijon_poupon.doc" "best mustard"

, Folder "programs"

[ File "fartwizard.exe" "10gotofart"

, File "owl_bandit.dmg" "mov eax, h00t"

, File "not_a_virus.exe" "really not a virus"

, Folder "source code"

[ File "best_hs_prog.hs" "main = print (fix error)"

, File "random.hs" "main = print 4"

]

]

]

Making a Zipper for Our Filesystem

Now that we have a filesystem, all we need is a zipper so we can zip and zoom around it, and add, modify, and remove files and folders. As with binary trees and lists, our breadcrumbs will contain information about all the stuff that we chose not to visit. A single bread-crumb should store everything except the subtree on which we’re currently focusing. It should also note where the hole is, so that once we move back up, we can plug our previous focus into the hole.

In this case, a breadcrumb should be like a folder, only it should be missing the folder that we currently chose. “Why not like a file?” you ask? Well,