Add one or more queue/steque types

[treeowl]

Idiomatic Haskell very often gets around using an explicit queue by partially imitating one with a lazy list. In a linear context, this doesn't always work out so well. In particular, suppose we have a thunk representing the generation of a list, and we discover that we actually don't need that part. Well, tough. We have to generate it anyway to consume each element. I think it would be useful to have some queues and output-restricted deques to work with, which could be used for things both internal and external. Some options:

1. Array-backed queues
2. Two-stack queues (traditional)
3. Scheduled banker's queues (optimal implementation will require some unsafe coercions for linearity)

Both traditional two-stack queues and banker's queues are actually output-restricted deques.

[aspiwack]

You leave me a little confused, my apologies. Can I ask you to scribble some code example of what you would like to do and find it problematic with linear types?

[treeowl]

I suspect what I'm really looking for here is an affine stream type, rather than a queue. That said, consider Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design by Okasaki. The simple (list-based) level-oriented solutions don't seem feasible; only the queue ones probably are.

[aspiwack]

Because I'm very slow, I just figured out that this was related to https://github.com/tweag/linear-base/issues/453#issuecomment-1556285703 :slightly_smiling_face: .

My thoughts right now:

• I agree that queues are useful; what was puzzling to me is that I was reading your original point as implying that some idiomatic Haskell code without queue now needs queues.
• For purely linear queues, amortisation is not much of an issue, as you are forced to use the queue single-threadedly. So you can use the two-list encoding without much worry.

[treeowl]

Amortization can be a performance issue in concurrent code, or when rebuilding has bad cache effects. It's been quite a while, but as I recall scheduled queues beat out amortized ones in some old logict-sequence benchmarks despite the additional complexity. However, scheduled queues need unsafe coercions because we don't yet have a story for linearity and lazy pattern matching.

[aspiwack]

Sorry, I mispoke: I meant that amortisation is easy because single-threadedness avoids all the issues with purely functional data structures that more sophisticated data structures avoid. In a function with linear data, you're guaranteed that (within the boundary of this function) the queue will be single-threaded.

That being said, an array-backed data structure would work great too.