Efficient Amortised and Real-Time Queues in Haskell | Hacker News Reader

Efficient Amortised and Real-Time Queues in Haskell

well-typed.com

72 pointsjkarni15 comments

In my experience, bankers' Queues (like the one presented in the article) are not the best persistent queue solution.

The Finger Tree (available in the Haskell standard library under Data.Sequence) is a really impressive data structure. It's persistent, it has O(log(min(n,len-n))) access and modification (which means O(1) cons, snoc, head, and last), and O(log(min(m,n))) concatenation.

In my testing, it was several times faster than the fastest banker's queue library I found.

I had an experience changing code from using priority queue using finger tree to using sorted lists (regular Haskell's lazy lists, sorted, not even merged!) and obtaining an order of magnitude speedup and reduction of memory consumption.

So I would like to advise staying away from finger trees and other interesting data structures when lists suffice.

In case of queues they are very sufficient.

What article lacks, is the performance comparisons.

I probably understand these concepts without knowing their official names. But man, sometimes I feel really dumb when I see phrases like "Queue Invariant" or "Amortised Complexity". It's nice that this article explains them simply.

At least in our field we didn't have to know these names to do well, and we don't need to know them to do our job. My commerce degree on the other hand, if I got the concept, but did not get the name, it's not worth anything to the examiner.

I used to scoff at the use of all these official names (to borrow your phrase), but over time I've found how useful they can be at precise communication.

Before I just thought they were pedantic or snobbish.

> I probably understand these concepts without knowing their official names.

It's been my observation that reading articles/posts written by Haskell programmers is a great way to be spend a fair amount of time being confused over things that you already understand, usually for this reason. In that sense, at the least, they're usually educational.

It's my suspicion that the most common path to becoming a Haskell programmer is to read too many of these sorts of things, to start using the terminology in your own writing and speech, then to find that no-one but Haskell programmers understand you anymore, leaving you no choice.

My fairly standard computer science education covered amortized complexity. You can't analyze the time complexity of a sensible vector type (i.e. "one step above raw array") without it.

Invariants are admittedly undersold in the curricula I've seen, but the idea comes up in many places. Most people ought to have at least encountered the idea in databases, where foreign key references provide basic invariants about referencing existing rows no matter what SQL you fling at them, for instance.

Haskellers borrow terminology from abstract math and CS because the concepts are just plain useful (for code reuse, performance, and safety) and it’s kinda pointless to rename them.

Of course we’re going to talk about these ideas, because Haskell makes it easy to apply them in the real world. And if you have the choice, why would you go back to a language where you don’t have that advantage?

As jerf said, amortized complexity is discussed in a CS2-style course (in the second semester) when implementing array lists, but invariants are also discussed in the same course when implementing binary heaps or balanced trees (typically AVL or red-black).

It's also plausible that loop or class invariants are discussed in a CS1 course to ensure that your objects don't end up in invalid states after the execution of a loop/method. But maybe the exact word "invariant" is not used as such here.

"Amortised complexity", a concept so esoteric that is used in the documentation of basic Java data structures: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayLis...

"The add operation runs in amortized constant time, that is, adding n elements requires O(n) time."

Perhaps a better way to think about it is that often when reading these sorts of articles, you realize that there's a name, and likely a corresponding rigorous definition and theory, for some concept which you had already understood intuitively. Once you've made that realization, you start to see the pattern yourself in other areas that you hadn't before, and to understand it more deeply.

Never thought lazyness could transform an o(1) operation into an o(n) as a side effect.

I thought memory management was hard to reason about in pure functional languages, but i never thought it could affect algorithmic complexity this badly.

http://accidentallyquadratic.tumblr.com/

Great blog with examples where something linear turns quadratic! :D

Most of the examples show that being this high at the abstraction level disallows you to properly evaluate the complexity of the code you are writing. Something that might look simple and linear can in fact have a quadratic behavior.

If you're talking about the discussion of head and snoc at the beginning of the article, laziness just moved the costs around - head becomes O(n) (from O(1)), but snoc becomes O(1) (from O(n)), because you only pay for the snoc costs when inspecting the queue with 'head'.

It can be stunning the first few times you see this sort of thing, but Haskell run time performance is not that hard to reason about it - is simply different from strict languages. As an experienced Haskeller I could see their point at the definition of the data structure and operations. In fact there is an entire data structure library built around this idea of O(1) snoc/appends, the dlist: https://hackage.haskell.org/package/dlist-0.7.1.2

Reply on news.ycombinator.com