Proposal: adding a Queue module in the stdlib

[Andrea Leopardi]

Hey there!

I love queues as a data structure. Erlang provides the :queue module and that's what you use in Elixir, but the API for :queue is "meh" at best. It's queue-as-a-last-argument, it has three different APIs (original, extended, Okasaki) and it's just not Elixir-y. I think queues make great candidates for an additional collection type in the Elixir standard library, so I propose to add a Queue module to the stdlib. The API for Queue that I imagined goes something like this:

• Queue.new/0
• Queue.put/2 and Queue.put_front/2
• Queue.get/1 and Queue.get_rear/1
• Queue.peek/1
• Queue.to_list/1
• Queue.join/2

We would also implement the following protocols for Queue:

• Inspect
• Enumerable
• Collectable

This way, we could manipulate queues as enumerables and do awesome things like Enum.into(enum, Queue.new).

To sum up, I think the problems with :queue are inconsistent API, terrible inspection (e.g., an empty queue looks like this {[], []} when inspected), non enumerability.

I threw together a short implementation of this (no comments, no tests, just as a proof of concept): https://gist.github.com/db432803f692771e489e. What does the Elixir community thinks?

[José Valim]

Thank you Andrea!

I am a little bit torn on queues. I have used them but only as the inner state of GenServer so I never really felt the need to make it an Elixir data structure because I am never passing it around. It is one of those things I am really on the fence, specially considering we can't really provide a faster implementation than Erlang's.

José Valim

www.plataformatec.com.br

Skype: jv.ptec

Founder and Director of R&D

--
You received this message because you are subscribed to the Google Groups "elixir-lang-core" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-co...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/6da32317-b3d4-439c-9ded-21786188179e%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Peter Hamilton]

Performance is really key here. It's difficult to make a general purpose immutable queue that performs well in most situations. It's not too difficult to make a decent queue that fits one use case. The result is that if you need a queue, you build it for your specific use case. If performance doesn't matter, using a list (pop and append) works in a pinch.

To view this discussion on the web visit https://groups.google.com/d/msgid/elixir-lang-core/CAGnRm4K2yyayMRV-y3Tia9bQkYNAhECMybQpYHyU29hiqcsnJA%40mail.gmail.com.

[Andrea Leopardi]

José, thanks for your feedback. You make a great point that I didn't consider at all: queues are often used as a "stateful" data structure. I myself pretty much only used queues as inner state for GenServers, never passing them around. I didn't mention performance on purpose because I know we can't make performance better than Erlang's implementation; my focus was very much on making the API and the data structure more Elixir-y (Enumerable, Collectable, inspection and so on).

I guess maintaining a Queue module would not be a huge thing because the implementation is pretty simple (and mostly delegation to :queue functions), but again, your points make very much sense and I'm not sure anymore it would make sense to add it.

[Booker Bense]

Would it make sense to implement Queue as a set of callbacks and functions similar 

to the way Set or Dict are implemented? 

That way you'd have standard functions but could match the implementation to your

use case.  

However, I'm not sure this generic implementation is that different from a List to be 

useful. One thing that comes to mind would be to add attributes to the data structure

about how the queue can be iterated. For example: :serial vs :parallel 

To me Queue implies list of tasks in some sense. That seems like a natural data 

structure for the dataflow kind of streaming that is on the roadmap. In this case 

the data would know what kind of parallelism it's capable of. Or is my OO mindset

skewing my view again? 

- Booker C. Bense 

[Ed W]

On 09/10/2015 14:09, Andrea Leopardi wrote:

I love queues as a data structure. Erlang provides the :queue module and that's what you use in Elixir, but the API for :queue is "meh" at best. It's queue-as-a-last-argument, it has three different APIs (original, extended, Okasaki) and it's just not Elixir-y. I think queues make great candidates for an additional collection type in the Elixir standard library, so I propose to add a Queue module to the stdlib. The API for Queue that I imagined goes something like this:

I previously wrote a "Priority Queue", which uses a roughly similar interface to the one you describe.  It has a fairly performant implementation using a pairing heap.

    https://github.com/ewildgoose/elixir_priority_queue/blob/master/lib/priority_queue.ex

I mention it mostly because it slightly widens the scope of your proposal. Hopefully it demonstrates the requirement that there is a "Queue" type of interface as well as a selection of Queue concrete types (perhaps something like we have with Dict/Map.

I would be happy to sync my function prototypes with yours if we deviate anywhere?

As an aside, I agree that whilst this may not make elixir stdlib, I DO think elixir core could help a lot guiding interface naming conventions. At the very least it would be nice if the multitude of competing Queue options which might emerge will at least use fairly standardised names for the interface functions

Cheers

Ed W

[Andrea Leopardi]

I am not particularly in favour of having Queue be a generic interface to different implementation as that I'd like to strive for simplicity (conceptually I think a queue is a very simple structure). Also, Dict is going away in future Elixirs so there's that :). That said, this could all fit the scope of an external queue library, which is not constrained to be "simple" anymore as it's not in the stdlib; the problem then becomes that you have to bring an additional dependency in your project, which is something I always think hard before doing.

[Saša Jurić]

I'm +1 on this. Having Elixir Queue would allow us to use all the goodies such as protocols and pipeline friendliness, so I think it's not just wrapping for the sake of wrapping.

[Vincent Siliakus]

Coincidentally I just implemented a fifo queue for a project last week, loosely based on Erlang's queue module. After reading this discussion I decided to model it completely after Erlang's queue module and added the join, to_list and Collectable protocol implementations that my previous queue implementation didn't have. It actually doesn't provide that much more than your gist, except that enumerating is less expensive, since the complete queue doesn't need to be converted to a list anymore. Anyway, you can find it here:

https://github.com/zambal/queue

-vincent

Op vrijdag 9 oktober 2015 15:09:29 UTC+2 schreef Andrea Leopardi:

[Vincent Siliakus]

Hi,

I cleaned up the code, fixed some ordering issues (yesterday's version behaved by default more like a stack than a queue), optimized the Enumerable implementation, borrowed Andrea's implementation for the Inspect protocol, which is much better that my initial quick and dirty implementation, and largely adopted Andrea's suggestions for names, as I think they're better that the names I initially picked. I only kept 'pop' instead of 'get' as I think 'get' doesn't explain that the element will be removed from the queue.

Andrea and all, do you have any other suggestions for my current implementation?

-vincent

[Ed W]

I quite like the names shift/unshift instead of pop_rear, et al?

However, put/pop/peek seem like the correct words for the main operations

Good luck

Ed W

[Robert Virding]

Having a double list like the erlang queue module does is a more efficient structure than just a single list.

Robert