Oh, interesting, I implemented a zipper in Elixir and came across gap buffers as a result while reading afterwards, but never implemented one/didn’t realize the normal implementation involved mutation… I was actually considering making a zipper protocol/library or something that abstracted the differences between (in my mind) a zipper-tree, a zipper-array or gap buffer, and maybe a zipper-map (which I’m a little fuzzier on utility/implementation of, but I guess for ordered/each traveral of k/v pairs with pausable/passable state etc).
I’d imagined the functional version of gap buffer as just a pair of lists each with the head of the list at the gap, and moving the gap just being an O(1) add/remove mutation on each list, but maybe I’m missing/forgetting something?
iex(1)> new = fn -> {[],[]} end
#Function<20.52032458/0 in :erl_eval.expr/5>
iex(2)> move_left = fn {[l|x],r} -> {x,[l|r]} end
#Function<6.52032458/1 in :erl_eval.expr/5>
iex(3)> move_right = fn {l,[r|x]} -> {[r|l],x} end
#Function<6.52032458/1 in :erl_eval.expr/5>
iex(4)> get = fn {[l|_],_} -> l end
#Function<6.52032458/1 in :erl_eval.expr/5>
iex(5)> drop = fn {[_|l],r} -> {l,r} end
#Function<6.52032458/1 in :erl_eval.expr/5>
iex(6)> insert = fn({l,r},v) -> {[v|l],r} end
#Function<12.52032458/2 in :erl_eval.expr/5>
iex(7)> from_list = fn lst -> {[],lst} end
#Function<6.52032458/1 in :erl_eval.expr/5>
iex(8)> z = new.()
{[], []}
iex(9)> z |> insert.(1)
{[1], []}
iex(10)> z = z |> insert.(1)
{[1], []}
iex(11)> z = z |> insert.(2)
{[2, 1], []}
iex(12)> z |> get.()
2
iex(13)> z = z |> move_left.()
{[1], [2]}
iex(14)> z |> get.()
1
iex(15)> z = z |> drop.() |> move_right.()
{[2], []}
iex(16)> z |> get.()
2
iex(17)> z = from_list.([1,2,3,4,5,6])
{[], [1, 2, 3, 4, 5, 6]}
iex(18)> z |> move_right.() |> move_right.() |> drop.() |> move_right.() |> insert.(42) |> move_left.() |> move_left.() |> move_left.()
{[], [1, 3, 42, 4, 5, 6]}
And there are tons and tons and tons of more styles that zipper’s are useful for including not just lists but as you hinted at also maps and other things. A zipper can easily walk along every node in a deep map for example.
Isn’t a zipper sort of the opposite to a functional queue (giving you O(1) access to somewhere in the middle of a collection, whereas a queue gives you O(1) access to the front and back of the collection)?
It is yep. Though you can finagle a queue into it by ‘inverting’ the queue so that the zipper point represent the beginning/end of the queue on each of its left/right sides like in my much earlier post.
Right! Hence my idea of a zipper protocol that could compose any number of zipper-variant data structures and unify interface etc.. but I don’t have a practical use case so haven’t been substantially motivated to make it I forget if I knew they were already all zippers or just that they could all be thought of as zippers, but I didn’t know of them before doing the exercism problem for it in elixir… reminded me of lenses and nathan marz’ specter library though IIRC those separate the zipper from the data it’s zipping so the same zipper can access any data in the same shape… Last i checked there were no lenses in Elixir, just a small discussion with Jose but that was a while ago and now it seems there are two! focus and elins, though I imagine that lenses are not as efficient as zippers, without looking at the implementation of either…
I’m in the process of building my own implementation of Queues and Deques in the (very much work-in-progress) library okasaki.
I now both have an amortized (with list reversing) and hard constant-time implementations of a single-ended queue and a double-ended queue, as well as implementations of Enumerable, Collectable and Inspect for them.
However, there are many functions of Enum that you cannot really use well with the queues, as your whole queue will be flattened to a single list. I’ll probably ending up re-writing 2/3 of the Enum-functions but then in a way that the part of the queue that is not consumed remains a queue. (Things like map, take, take_while, drop, drop_while etc).
It would be great if someone can review the implementations. I also think that benchmarking the two different approaches is (amortized, hard constant-time) for different sizes of queues is a good idea.
Cool, though I’m curious what a version of the queue and deque using a map would be like? Basically have the keys be integers and also store a start and end value to look up the start and end of the queue/deque (either storing the start/end in the map or perhaps have a top-level tuple/record store that storage map and the start/end indexes). I wonder how that would perform…
I’d had the same thought (tuple, hadn’t thought of storing the end values in the map). A hashmap has O(1) for all access, insert, delete. So the questions are: What’s the constant factor like compared to the amortized cost of the 2-list implementation, and how does garbage generation compare?
In that case you are doing the ‘map as pointers’-approach to get a data structure supporting fast random access of any elements inside. This is the approach that I took for the Vectors in the Tensor library. Obviously the main drawback of this is that the data structure is bigger, and looking up elements in a map sequentially is still significantly slower than iterating over a list.
