Elixir needs a FIFO type?

That is only because Elixir pipes into the first arg instead of the last as is normal functional design (and of which ‘most’ erlang libraries follow the standard functional design of putting the ‘structure’ argument in last place, Elixir is the odd one out. ;-)).

Probably slower actually. Simple list manipulation like this is so simple (and the :lists.reverse native function is so fast) that the overhead of a NIF would likely exceed the calls as they are now.

Ahh so true, I remember those younger Erlang days. ^.^;

I don’t know if I’m more lazy or what, but I use zippers themselves in those places. I should make a proper zipper library sometime…

I’ve made/used gap buffers in C++, and I don’t think they’d fit in as well here, they rely on mutability in their standard designs. You could make one that is not but it would end up being slower. A zipper basically is the functional form of one anyway with limitations so mutability is not needed. :slight_smile:

/me loves zippers, uses them surprisingly often

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?

That is still a zipper. :slight_smile:

A cursor style zipper is one that is used like:

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. :slight_smile:

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. :slight_smile:

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 :slight_smile: 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…

1 Like

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.

2 Likes

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?

1 Like

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.

1 Like

I’ve just been using Erlang’s :queue module. Works like a charm, and built in.

https://github.com/sergiotapia/magnetissimo/pull/72/files#diff-c0b040e6dc65b53a4928373ee6442ff5R34

@sergio
After messing with queues a lot today, here is what I dislike about :queue:

  1. The datatype it works with does not (and cannot) implement protocols.
  2. The datatype it works with does not show to the user what it is: It is indistinguishable from any other two-tuple. Introspection is a great tool to help a new person who reads your code (or a stacktrace).
  3. The :queue module has three different name aliases for most functions.
  4. There are only a few functions that allow you to manipulate :queues in an enumerable-like way. The only other approach you can take is to first convert it to a list.
  5. It cannot be used in pipes as it follows Erlang’s convention to have the most significant argument as last argument.
  6. Because it is an Erlang module, we do not have documentation for it in IEx.
  7. insertion and extraction are amortized O(1). Its implementation means that if someone first inserts n = 100_000 items, then retrieving the first inserted item afterwards is going to mean that this list with a n = 100_000 elements first needs to be reversed. As @OvermindDL1 noted: List reversal is a native piece of code that is relatively fast; still I expect that at a certain n, it becomes too slow and too unpredictable, and a hard constant time variant should be used instead.
1 Like

Like how every language with piping pipes? Elixir is the odd one out here. :wink:

Remember that Erlang has a last-place kind of piping call too with tuple-calls: ^.^

iex> defmodule Testering do
...>   def blorp(x, {Testering, y}), do: x + y
...> end
{:module, Testering,
 <<70, 79, 82, 49, 0, 0, 4, 228, 66, 69, 65, 77, 69, 120, 68, 99, 0, 0, 0, 164,
   131, 104, 2, 100, 0, 14, 101, 108, 105, 120, 105, 114, 95, 100, 111, 99, 115,
   95, 118, 49, 108, 0, 0, 0, 4, 104, 2, ...>>, {:blorp, 2}}
iex> {Testering, 32}.blorp(10)
42
iex> t = {Testering, 32}
{Testering, 32}
iex> t.blorp(10)
42

/me really likes tuple calls, they are so useful in so many ways, especially as a form of first-class modules

Oh yes, I am totally aware that Elixir is the ‘odd one out’. That being said, there is not really a ‘better choice’; it is an endianness-type of problem (in Haskell, which only has arity-1 functions, it definitely makes more sense to do significant-last because of currying, but Erlang does not support this and neither does Elixir). Elixir chose it differently from Erlang and Haskell, and we will need to cope with it because it will not change (in the forseeable future, and possibly ever). Therefore, something that adapts to Elixir’s form of calling would be preferred by me when writing Elixir code.

Easy enough to fix. ^.^

defmodule ToLast do
  defmacro to_last(arg, {fun, meta, args}) when is_list(args) do
    {fun, meta, args++[arg]}
  end
end

Used like:

iex> import ToLast
ToLast
iex> q = :queue.new()
{[], []}
iex> q = q \
...> |> to_last(:queue.in(1)) \
...> |> to_last(:queue.in(2)) \
...> |> to_last(:queue.in(42))
{[42, 2], [1]}
iex> :queue.out(q)
{{:value, 1}, {[42], [2]}}

Though would be nice if |> could some how know (protocol? or query something for a list at compile-time?) or something like ~> could be used for the end. ^.^

I could imagine a defdelegate flip:true or something like that to bring in a function and cast to another module but flip the last to the first argument. That would be convenient to make an Elixir Queue module that delegates to Erlang’s :queue but flipping the order in only like 4 lines of code. ^.^

1 Like

@OvermindDL1 Thank you for showing how to write a macro wrapper to flip the arguments passed to a function.

I do feel however that we’ve become a little side-tracked.

Even wrapping :queue like that does not fix its other shortcomings:

I’m going to benchmark the hard real-time vesion of the queues and deques vs. the amortized versions (which includes :queue’s) to see how performant they are.

As an aside: I really want to create an Traversable(Trav?) for Elixir, to be used instead of Enum when you do not want to throw away the structure of the data you have. :grin:

1 Like

Right. Which is why, while the macro to flip arguments around is useful, it’s not that useful to have a macro that just does that to all exported functions. So one would want to wrap the queue with more explicit code:

  1. Are you sure you cannot implement Enumerable on top of a queue??? Admittedly, I haven’t tried it, but I don’t see why it’s not possible.

  2. Clearly the exact kind of thing to solve with a wrapper: return {:queue, the_actual_queue}

  3. An Elixir queue would clearly not replicate that.

  4. Back to 1, if the Enum protocol can be implemented over a queue…

  5. Yep, wrap it.

  6. One of the reasons that I think Elixir needs its own deque. This is too fundamental of a data structure to expect people to rummage around in the Erlang docs.

  7. Agreed.

[edit] Bah humbug, got going too fast and forgot that I wanted to add my own 8, that the return types, and use of {:error, …} vs raising exceptions is not really Elixirish. And there are a handful of xxx! functions that should probably be added. At this point I’ve got a lot of it already written, but on top of deque, which I’m not sure is the absolute best choice.

1 Like

Because this topic was the catalyst that started it: Okasaki has been released on Hex.PM!

It contains four different implementations of queues (two queues, two deques). In the near future, a wrapper around :queue will be added as well.

Okasaki implements a slew of protocols and behaviours that should make it as easy and straightforwards to use as possible.

1 Like