[ACCEPTED]-What is the Zipper data structure and should I be using it?-zipper
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.
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.
This article is related to Haskell, but it also explains 2 zippers fairly well and it should be easy 1 to abstract from the Haskell-specifics.
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.
Basic 3 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 2 to the left. Similarly the other functions 1 shift the focus to other grid cells.
More Related questions
We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.