Hacker News Reader

Comment by mastermedo | Hacker News Reader

I don’t understand why wouldn’t you just use a list and an index. You can always access list[index+1] or list[index-1] or list[0] or list[list.length-1].

What is the benefit here?

View on HN

Firstly, accessing an arbitrary list index is O(N), whilst a Zipper can access its focus in O(1) (shifting the focus is O(1) for both Zippers and list+index)

Secondly, using an index forces us to do bounds checks, keep track of the length (or re-calculate it at O(N) cost), etc. whereas a Zipper is "correct by construction"; i.e. every value of type (List[A], A, List[A]) makes sense as a zipper; whereas many values of type (List[A], Nat) don't make sense as zippers; e.g. ([], 42) doesn't make sense. Our logic also becomes easy for pattern-matching, e.g. in Scala:

    myZipper match {
      case Zipper(xs, x, y::ys) => Zipper(x::xs, y, ys)
      case z => z
    }

Also, your example of 'list[index-1]' is more complicated than it first appears. In particular, what is the type of 'index'? If it's an integer, then at least half of the possible values are meaningless (negative numbers); if its a natural (AKA unsigned integer), then it's not closed under subtraction (i.e. we have to worry about underflow)!

Thirdly, Zippers can be unbounded in both directions (i.e. the lists can be "infinite"/co-inductive). For example, they're great for implementing Turing machines, starting with an infinite blank tape in both directions. https://en.wikipedia.org/wiki/Coinduction

Fourthly, Zippers have more sharing. Here's an arbitrary example: say we have a zipper like this:

    ([c, b, a, ...], elem, [x, y, z, ...])

If we shift right, replace the focused element with 'newElem', then shift right again, we'll get this zipper:

    ([newElem, elem, c, b, a, ...], y, [z, ...])

Those operations take O(1) time and O(1) memory (and produce O(1) garbage, if we're no longer using the old zipper). In particular, since the tails of the lists ([c, b, a, ...] and [z, ...]) are unchanged, the same pointers will appear in both the old and new zippers; there has been no copying. This is important, since those lists could be arbitrarily long (or infinite!).

In contrast, if we did these operations on a list+index, everything before the replaced element would need to be reallocated; i.e. [..., a, b, c, elem, _] would need to be copied, since _ has changed from 'y, z, ...' to 'newElem, z, ...'. That requires O(N) memory allocation, takes O(N) time to do the copying (and produces O(N) garbage, if we don't want the old zipper).

And they can be generalized to work on any kind of trees instead of just lists.

> accessing an arbitrary list index is O(N)

I think you mean linked-list here. Parent is talking about "arrays".

> I think you mean linked-list here

Yes, I specified this explicitly, e.g. "The Zipper acts like a linked-list with a cursor" and "Where [a, b, c] denotes a singly-linked list".

> Parent is talking about "arrays"

You're using quotation marks, but I don't see what you're quoting? The parent explicitly says: "a list and an index"

In any case, arrays come with most of the same problems I mentioned for lists:

- They have invalid states, e.g. ([], 42)

- They require bounds-checking, a consistent notion of subtraction on the index type, etc.

- They can't be infinite

- They require O(N) time, O(N) memory (and O(N) garbage if we're discarding the old value) to replace the focused element

- etc.

Plus, arrays come with all sorts of extra gotchas, like buffer-overflows, pre-allocation/re-allocation decisions, over/under-provisioning, etc.

The benefit is the data sharing between the tails. You can very cheaply get a copy of zipper with the data at (or around) the focused element changed while also keeping the original data unchanged. Admittedly, this is something people in functional programming languages probably care much more about.

This zipper stuff is for immutable data structures.. For us normal folk that just use & abuse array's we don't need zippers. :-). Just kidding. I am dieing to find a use for zippers tho, i'm not a functional programmer.

A list and an index creates the possibility that the index is out of bounds, and then your code probably has to check for that scenario and figure out how to handle it.

With a zipper such a scenario isn’t possible.

Reply on news.ycombinator.com