Stack Overflow
Stack Overflow

Questions tagged [zipper]

A zipper is a technique of representing a data structure so that it is convenient for traversal and updates, especially in pure functional languages.

A zipper is a technique of representing an aggregate data structure so that it is convenient for writing programs that traverse the structure arbitrarily and update its contents, especially in purely functional programming languages.

The basic idea is that an existing list- or tree-like data structure is augmented with a representation of a "focus" on a single item in the tree in a way that permits efficient lookups and updates at the focus point.

A simple example is a zipper for a list, consisting of a pair of two lists. For example, the position of 3 in the list (1,2,3,4,5) is represented by the pair ((2,1),(3,4,5)). To insert a new item or replace 3 with another item with this representation can be done in constant time since 3 is at the head of the second list of the pair. Traversing the list is similarly easy: remove the head of either list and cons it with the other list.

You can read more about zipper in Haskell in the Haskell Wikibook.

126 questions
128
votes
7 answers

Cleaner way to update nested structures

Say I have got following two case classes: case class Address(street: String, city: String, state: String, zipCode: Int) case class Person(firstName: String, lastName: String, address: Address) and the following instance of Person class: val raj =…
missingfaktor
  • 90,905
  • 62
  • 285
  • 365
113
votes
1 answer

Understanding why Zipper is a Comonad

This is a follow-up to the answer to my previous question. Suppose I need to map each item a:A of List[A] to b:B with function def f(a:A, leftNeighbors:List[A]): B and generate List[B]. Obviously I cannot just call map on the list but I can use the…
Michael
  • 41,026
  • 70
  • 193
  • 341
83
votes
3 answers

Zipper Comonads, Generically

Given any container type we can form the (element-focused) Zipper and know that this structure is a Comonad. This was recently explored in wonderful detail in another Stack Overflow question for the following type: data Bin a = Branch (Bin a) a (Bin…
J. Abrahamson
  • 72,246
  • 9
  • 135
  • 180
58
votes
4 answers

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

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…
avp
  • 4,895
  • 4
  • 28
  • 40
47
votes
3 answers

Zipper for creating xml requests?

How can one create an XML request conforming to an XSD such that the request is valid? One way would be to create the whole request and then verify it on the XSD. Is there a way to create a request while walking the schema? The first thought that…
Akshat
  • 577
  • 3
  • 6
30
votes
4 answers

What are the differences between lenses and zippers?

This is an example of using a zipper in Haskell: data Tree a = Fork (Tree a) (Tree a) | Leaf a data Cxt a = Top | L (Cxt a) (Tree a) | R (Tree a) (Cxt a) type Loc a = (Tree a, Cxt a) left :: Loc a -> Loc a left (Fork l r, c) = (l, L c r) right ::…
hawkeye
  • 34,745
  • 30
  • 150
  • 304
28
votes
4 answers

How to combine slices into a slice of tuples in Go (implementing python `zip` function)?

Sometimes, it's convenient to combine two lists into a tuple using zip built-in function in Python. How to make this similarly in Go? For example: >>> zip ([1,2],[3,4]) [(1,3), (2,4)]
holys
  • 13,869
  • 15
  • 45
  • 50
26
votes
1 answer

How to make a binary tree zipper an instance of Comonad?

I want to make a binary tree zipper an instance of comonad, but I can't figure out how to implement duplicate properly. Here is my attempt: {-# LANGUAGE DeriveFunctor #-} import Data.Function import Control.Arrow import Control.Comonad data BinTree…
Javran
  • 3,394
  • 2
  • 23
  • 40
25
votes
2 answers

Zipper like data structure with more than one cursor

The Zipper data structure is great when one wants to traverse a tree and keep the current position, but what data structure one should use if they want to track more then one position? Let me explain with examples: Someone on the #haskell channel…
Peter Jankuliak
  • 3,464
  • 1
  • 29
  • 40
23
votes
3 answers

Two-dimensional zipper

Inspired by the recent question about 2d grids in Haskell, I'm wondering if it would be possible to create a two-dimensional zipper to keep track of a position in a list of lists. A one-dimensional zipper on a list allows us to really efficiently…
deontologician
  • 2,764
  • 1
  • 21
  • 33
21
votes
1 answer

How well do zippers perform in practice, and when should they be used?

I think that the zipper is a beautiful idea; it elegantly provides a way to walk a list or tree and make what appear to be local updates in a functional way. Asymptotically, the costs appear to be reasonable. But traversing the data structure…
Rob Lachlan
  • 14,289
  • 5
  • 49
  • 99
19
votes
2 answers

Are all differentiable types Monads

Given a differentiable type, we know that its Zipper is a Comonad. In response to this, Dan Burton asked, "If derivation makes a comonad, does that mean that integration makes a monad? Or is that nonsense?". I'd like to give this question a specific…
Cirdec
  • 24,019
  • 2
  • 50
  • 100
18
votes
1 answer

Idiomatic Scala translation of Kiselyov's zippers?

Oleg Kiselyov showed how to make a zipper from any traversable by using delimited continuations. His Haskell code is quite short: module ZipperTraversable where import qualified Data.Traversable as T import qualified Data.Map as M -- In the…
Mike Stay
  • 1,071
  • 8
  • 17
17
votes
3 answers

Comonadically finding all the ways to focus on a grid

{-# LANGUAGE DeriveFoldable #-} {-# LANGUAGE DeriveFunctor #-} {-# LANGUAGE DeriveTraversable #-} import Control.Comonad import Data.Functor.Reverse import Data.List (unfoldr) First some context (ha ha). I have a zipper over non-empty lists. data…
Benjamin Hodgson
  • 42,952
  • 15
  • 108
  • 157
16
votes
1 answer

What are scars useful for?

In the paper titled "The Zipper" by Huet, he also mentions scars as a variation of zippers. Compared to zippers, which became pretty well known in the Haskell community, scars are pretty much unheard of. There is very little information about them…
The Red Fox
  • 810
  • 6
  • 12
1
2 3
…
8 9