[ACCEPTED]-What is the Zipper data structure and should I be using it?-zipper

Score: 60

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

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

Score: 17

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

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

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

Score: 9

0

Score: 5

Score: 0

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

``````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 2 to the left. Similarly the other functions 1 shift the focus to other grid cells.

More Related questions