-
In my work with Elixir, one of the few things that I’ve really found missing is an efficient FIFO.
-
Do others agree with the need?
-
If so, and if no one else is working on it then I’ll volunteer to wrap Erlang’s queue class into an Elixir-idiomized Queue.
1 Like
I usually just make my own zipper for that, it’s a simple 2-tuple that allows efficient ‘rear’ (and front technically) insertion as well as efficient ‘front’ (and rear technically) popping with an occasional :lists.reverse() flipping.
Yeah, the list.reverse hacks are great when you’re dealing with short queues. I’ve come across the one project now where I’m dealing with longer queues and I don’t want to do that.
(I’m assuming I’m understanding what you’re doing here… But since I’ve never actually implemented that, maybe I’m imagining it to be worse performing than it is.)
It is just a 2-tuple like:
iex> newFifo = fn -> {[], []} end
#Function<20.52032458/0 in :erl_eval.expr/5>
iex> pushFifo = fn({l,r},x) -> {l,[x|r]} end
#Function<12.52032458/2 in :erl_eval.expr/5>
iex> popFifo = fn {[f|l],r} -> {f, {l,r}}; {[], r} -> case :lists.reverse(r) do []->throw "BLARGH-EMPTY"; [f|l]->{f, {l,[]}} end end
#Function<6.52032458/1 in :erl_eval.expr/5>
iex> f = newFifo.()
{[], []}
iex> f1 = f |> pushFifo.(42) |> pushFifo.(16)
{[], [16, 42]}
iex> {result, f2} = f1 |> popFifo.()
{42, {[16], []}}
iex> {result, f3} = f2 |> popFifo.()
{16, {[], []}}
iex> {result_boom, f4} = f3 |> popFifo.()
** (throw) "BLARGH-EMPTY"
And the reverse function is VERY fast, it is not a usual bottleneck anyway even with large lists.
8 Likes
I ran into queue in the GenStage documentation - and as such I don’t see a big issue with using Erlang libraries directly when they are not exposed through Core Elixir (possibly adapted through a super thin wrapper tailored to the specific use case without covering the full capability).
I think Elixir developers should embrace the Erlang libraries - not hide them away.
7 Likes
The :queue module is the answer. It works on the same principle that @OvermindDL1 described.
5 Likes
Yes, I was asking about wrapping it…
I think that aside from the primitives which are already wrapped in :elixir-application, the most idiomatic way to wrap erlang modules and libraries is to use them directly.
2 Likes
I disagree. The native queue library cannot be used in a pipeline; its use, to me, sticks out as very non-idiomatic elixir.
I agree that :queue is not nice to pipe, and also not nice to intropect.
Its implementation itself, as a purely functional queue à la Okasaki, is wonderful.
I have used EQueue in the past, which is an Elixir wrapper around :queue.
I am unsure about my opinion of needing a queue inside of the standard library. FIFO queues are not used that often in functional programming (at least in the projects I have worked on). The most important one, the actor model message mailbox, is abstracted away from us.
I do wonder how a queue NIF would look like, though :D.
There is one serious issue with the :queue module and that is that there 3 interfaces to the module, which makes it a right mess. Keeping track of which is which is a problem. 
If you are going to do an elixir Queue module then pick one and stick with it.
If you do your own elixir Queue there is really no reason to interface the erlang one as the implementation part is so straight forward it is probably less code to do it yourself. I needed a queue with bounded length and found it easier to write it directly myself rather than put a wrapper around queue.
Yes, I was absolutely thinking a single Elixirish interface, implemented on a single one of the queue interfaces.
BTW, I focussed on FIFO because that’s what’s not built in, but really an Elixir Queue module should be a deque…
I’d not previously read up on the 2-list, reverse the rear when making it the front, technique enough to realize that the amortized cost of the list reversing is O(1). I’d been thinking of it in terms of: yeah, reverse might be pretty fast, but if you’re popping off thousands of times per second reversing would become significant–in fact, it doesn’t become significant overall, even though it does still have a crappy worst case.
You only need to reverse when the front queue is empty, and that is generally not for every element. But yes, it is amortized so sometimes it may take some time.
It’s exactly what I was looking for. Thing is, I just used Erlang’s dequeue and have taken a long time to getting around to having time to work on this. So long in fact, that when I first had this question that project didn’t yet exist.
Should have searched again before posting!
But I still think the deque is fundamental enough it should be part of the standard libraries. So that question still remains as to whether I’m alone on that.
@sribe: It is possible to spread out the reversing step across all O(1) operations, ensuring that the (double-ended) queue will have a stable O(1) running time, rather than sometimes a sudden O(n) worst case. (See Okasaki’s paper on this. They are really quite marvelous 
).
@rvirding: From your post, I gather that :queue itself is written in Erlang, where until now I had assumed that it was implemented in native C for increased efficiency. If it is indeed non-native code, it makes a lot more sense to write a version in Elixir that does not wrap it directly.
As for the three interfaces: Do they operate on different structures underwater, or are they just different names for the same operations?
Different names. One of the interfaces uses push and push_r while another says cons and snoc for front and back appending, don’t remember the last one. But all interfaces are working on a 2tuple with lists. Not even tagged.
1 Like
Yes, they all work on the same data structure so if you really wish to confuse the enemy, er your users, then you can mix interfaces.
2 Likes
This expresses how I just felt about the gen_statem documentation (from a newcomer perspective) - that page could really benefit from separate
state_functions[state_functions, state_enter]handle_event_function[handle_event_function, state_enter]
views.
(Sometimes I wonder whether people too familiar with the subject matter should be kept away from writing documentation - often the information dense narrative makes perfect sense to anybody who already has all the details in their head - but tends to overwhelm neophytes who are still struggling to stuff all the “relevant” details into their heads. 
)
2 Likes
If it’s simply a queue, I guess you’d be using it more as a gap buffer? though I guess the zipper is more general version of same idea… but yeah, that’s a good call
