_______ __ _______
| | |.---.-..----.| |--..-----..----. | | |.-----..--.--.--..-----.
| || _ || __|| < | -__|| _| | || -__|| | | ||__ --|
|___|___||___._||____||__|__||_____||__| |__|____||_____||________||_____|
on Gopher (inofficial)
URI Visit Hacker News on the Web
COMMENT PAGE FOR:
URI Zippers: Making Functional "Updates" Efficient (2010)
clarkmoody wrote 1 hour 44 min ago:
I've used the zipper concept with lists for making impossible states
impossible [0] in the context of Rust programs. The rich enum type in
Rust creates opportunities to avoid bugs by baking small state machines
into the code everywhere, like loading data in the linked example.
A concrete example is for managing the active item in a list. Instead
of storing the active item as an index into the vector like this:
struct List {
items: Vec,
active: usize,
}
...which two the glaring impossible states. The vector can be empty, or
the index can be outside the vector. Each time the active item is
desired, we must check the index against the current state of the list.
Instead, we can use the zipper concept so we always have a concrete
active item:
struct List {
prev: Vec,
active: T,
next: Vec,
}
Switching to a different active item requires some logic internal to
the data structure, but accessing the active item always results in a
concrete instance with no additional checks required.
[0]:
URI [1]: https://sporto.github.io/elm-patterns/basic/impossible-states....
johnfn wrote 22 min ago:
I tend to like the idea of making impossible states impossible, but
your particular example seems to have a number of negative tradeoffs.
For one, it's more complex than the original data structure - a
simple call like .map() is now a fairly chunky operation, and if you
want to filter after that, you really have a mess on your hands.
Additionally, you seem to have traded off one set of "state we
shouldn't allow to be represented" for another. For instance, you
could have mistakenly included `active` in `prev` or `next`. That is
something you couldn't have done in the initial version.
hombre_fatal wrote 1 hour 16 min ago:
What does the second List impl offer over the first one?
It's the API that makes something impossible to misuse, and they
could offer the same API like List.create(x: T, xs: T[]), but the
first one is simpler.
contificate wrote 2 hours 50 min ago:
There's a neat paper where they implement basic blocks (in a control
flow graph) as zippers ( [1] ). The neat part is that - due to how the
host language works (mutation having the cost of invoking the write
barrier) - their measurements show that the zipper version is more
performant than the mutable version.
URI [1]: https://www.cs.tufts.edu/~nr/pubs/zipcfg.pdf
xdavidliu wrote 3 hours 4 min ago:
i was messing around on hackerrank a few years ago and one of the
problems involved implementing Huet's zipper tree, which I did in
haskell. it was quite fun
URI [1]: https://github.com/xdavidliu/fun-problems/blob/main/zipper-tre...
thom wrote 3 hours 15 min ago:
I've built quite a lot of functionality on top of Clojure's version of
this. For deeply nested stuff it's great, necessary even. But for
shallow sequences where you're mostly doing complex logic looking back
and forth, I genuinely think you're better off building some sort of
parser combinator solution where you can more naturally match multiple
conditions over long ranges, and alter the output as you send it out,
transducer-style. You're also much more likely to end up with good
performance compared to the constant recursive navigation you do with
zippers.
macmac wrote 3 hours 25 min ago:
Zippers are part of Clojure API (clojure.zip). They take a bit of work
to get used to, but once you get it they are an amazing way of making
"transactional" "changes" to immutable data structures.
sevensor wrote 3 hours 46 min ago:
I can see how this is useful if youâre repeatedly updating the same
part of a tree. I canât quite see how to use this approach for random
edits. Seems like youâre back at recreating all the nodes back up to
the root every time?
agentultra wrote 3 hours 5 min ago:
Youâre right! For random access and edits youâll need a different
solution. Maybe some monads to encapsulate the mutations.
DIR <- back to front page