What is the Zipper data structure and should I be using it?

Question

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?

I don't know, but that wikipedia article is totally incomprehensible. Hence the confusion — 1800 INFORMATION, Dec 19 '08 at 09:13
[This article](http://en.wikibooks.org/wiki/Haskell/Zippers) is related to Haskell, but it also explains zippers fairly well and it should be easy to abstract from the Haskell-specifics. — Magnus, Dec 20 '08 at 15:34

score 60 · Accepted Answer · answered Dec 19 '08 at 09:28

60

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.

answered Dec 19 '08 at 09:28

namin

37,139
8
58
74

I mean, it clarified the "zipper" structure, but not the update method. – avp Dec 19 '08 at 10:01
Wait, how can I reverse the tree?? – avp Dec 19 '08 at 10:15
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 Dec 19 '08 at 10:32
10

@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 Apr 09 '10 at 18:53
12

@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 Apr 09 '10 at 20:59
@namin _"But usually, a list has **primitive accessors** for the head **and the rest**"_. What do you mean exactly? (are you referring to **linked lists** here? or something else?). Separately, why do you say _"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"_? A list could be implemented as e.g. a (dynamic) **array** or **linked** list, and in either case you would **not** need to copy those first n elements (although you may need to traverse them). – Amelio Vazquez-Reina Feb 27 '20 at 20:26

score 17 · Answer 2 · edited Jul 22 '16 at 07:02

Here is a very nice article explaining using the zipper for a tiling window manager in Haskell. The Wikipedia article is not a good reference.

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.

score 9 · Answer 3 · answered Aug 09 '13 at 22:01

9

Learn You a Haskell also has a great chapter about zippers.

answered Aug 09 '13 at 22:01

thSoft

21,755
5
88
103

score 0 · Answer 4 · answered Jan 23 '22 at 03:36

The code focuses on a cell like this picture shows. There are areas above,below, to the left and to the right. We move over this grid. The focus is the green square.

Basic Haskell

type cell = { alive : bool ; column : int ; row : int }
;;

type grid = {gamegrid : cell list list}
;;

type gridzipper  =
             { above : grid
             ; below : grid
             ; left  : cell list
             ; right : cell list
             ; focus : cell }

let left g =
match g.left with
 [] -> None 
| hd::tl ->  let newgridzipper = { g  with focus = hd; left = tl; right = g.right @ [g.focus] } in
             Some(newgridzipper)
;;

The left function moves the focus to the left. Similarly the other functions shift the focus to other grid cells.

What is the Zipper data structure and should I be using it?

4 Answers4

Linked

Related