views:

703

answers:

3

The question is simple: I cannot understand the Zipper data structure.

My question is related to its uses with a Tree.

I want to understand how can I change the tree node using zipper. And how not to copy the whole tree (or the most part of it).

Please, clarify if I'm wrong with zipper. Maybe it cannot help with the tree update?
Or, maybe, it is possible to update the tree and I just cannot see the way?

+9  A: 

Let's start with the Zipper-analog for lists. If you'd like to modify the nth element of a list, it takes O(n) because you have to copy the n-1 first elements. Instead, you can keep the list as a structure ((first n-1 elements reversed) nth element (remaining elements)). For example, the list (1 2 3 4 5 6) modifiable at 3 would be represented as ((2 1) 3 (4 5 6)). Now, you can easily change the 3 to something else. You can also easily move the focus left ((1) 2 (3 4 5 6)) and right ((3 2 1) 4 (5 6)).

A zipper is the same idea applied to trees. You represent a certain focus in the tree plus a context (up to parents, down to children) which gives you the whole tree in a form where it's easily modifiable at the focus and it's easy to move the focus up and down.

namin
Whoah,the first part is reversed! It helps, thanks!
avp
I mean, it clarified the "zipper" structure, but not the update method.
avp
Wait, how can I reverse the tree??
avp
Well, for trees, it's not exactly reversed. The zipper is focused on some node of the tree and consists of the children of that node and the context of that node (the tree with a hole instead of the node). See http://www.haskell.org/haskellwiki/Zipper
namin
@namin: one question: Why do we need to reverse the first `n-1` elements? I have absolutely no idea what purpose that serves. Please explain.
Lazer
@eSKay: Thoughtful question. You wouldn't need to if it took constant time to get any element in a list. But usually, a list has primitive accessors for the head and the rest, so then the rationale for reversing the first n-1 elements is clear: you quickly want to get the previous element and this way it's the head.
namin
@namin: thanks!
Lazer
+5  A: 

Here is a very nice article explaining using the zipper for a tiling window manager in Haskell. The person who wrote the wikipedia article should be shot.

In short, the zipper is a pointer or handle to a particular node in a tree or list structure. The zipper gives a natural way of taking a tree structure and treating it as though the tree was "picked up" by the focused node - in effect, you get a second tree without requiring additional copies made of the original tree or affecting other users of the tree.

The example given shows how you have the windows originally sorted by location on the screen, and then to model focus you use a zipper pointed at the focus window. You get a nice set of O(1) operations such as insert and delete without having to special case the focus window or write additional code.

1800 INFORMATION
Maybe you could edit the Wikipedia article?
Norman Ramsey
+2  A: 

This article is related to Haskell, but it also explains zippers fairly well and it should be easy to abstract from the Haskell-specifics.

Magnus