So this is only tangentially related, but it's all bloody neat, so I'm going to mention it anyway.

First, keeping a length of a list, as part of the library implementation, is a bad idea, because due to how immutability works, you'd need to keep a length from -every item in a linked list-. That is, rather than

  [4, 3, 2, 1]

you would need to have

  [{4, 4}, {3, 3}, {2, 2}, {1, 1}]

Why? Because adding a new element to the head of a list needs to be O(1), -and- maintain the existing list. That is, if I have

  List1 = [4, 3, 2, 1].

I need to be able to do

  List2 = [5 | List1]

That is, List2 is now

  [5, 4, 3, 2, 1]

and List1 remains unaffected. So both List1 and List2 would need to still know their lengths, as would any other variables with heads further down in the list.

So we have ~doubled the memory usage of a list, in that we need both a pointer (to the contents), and an integer, for each cell of the list. We can't simply store a 'total' value for a list (well, we could, and then every time we perform -any- operation on a list, that generates a new list(s) we re-calculate the length for it/them. Which would be a pain to code, results in a lot of extra garbage (since the intermediate values of the counter are thrown away, again, immutable), is unnecessary...and is actually impossible in lazy languages like Haskell that allow infinite lists. Quite frankly, in functional languages you don't need the length enough to go through such hassles, and when you do, yeah, it's easy enough to write it for your one use case).

And that said, we don't need any of that noise for implementing an efficient queue. An immutable queue in Erlang is implemented via Okasaki's queue implementation (though with a recognizable API by default; Okasaki's API is still there). This is actually a really cool data structure, and has parallels to the interview question "how would you implement a (double ended) queue using two stacks".

In short, it looks like this -

  {[], []}.

Where you have a tuple of two elements; two lists (and an immutable list works identically to a stack; operations upon the head of it work in O(1) time)

Enqueue 1 at the front ->

  {[1], []}

Enqueue 2 at the front; note that this is actually stacking the 2 in front of the 1 ->

  {[2,1], []}

Dequeue examines the second list, sees it's empty, reverses the first list, puts it in for the second (and an empty list in the first), and pops off the top of it, a la ->

  {[2,1], []} -> {[1, 2], []} -> {[], [1, 2]} -> {1, {[], [2]}}

Where 1 is your return value, and {[], [2]} is the new queue.

Further enqueues keep going onto that first list, dequeues come off the second, until it's empty, whereupon the first list is reversed again and placed in for the second. Etc.

This has an amortized constant time enqueue and dequeue, despite being immutable, and a constant time 'is_empty' check, where you just check each list to see if it's empty or not (easily doable by checking to see if it pattern matches [] or [_ | _].

Pushing onto the start of the second list, and pulling off the first, allows you to work on the other end of the queue.

So all your usual operations for a double ended queue work in the same big-O time as for the mutable implementation, but you maintain immutability.

The problem here is that the implementation relied on an O(n) behavior, when all it needed was an O(1) one.

While the article states "The problem is not with erlang:length() being slow. It’s about being unpredictably slow.", I would counter that asking for length when you just want to see if it's empty or not is INDEED the problem. Length explicitly tells you it will traverse the list, and yes, it makes no guarantees about where the elements of the list are in memory. Same as in every other language. Because contiguous pointers in memory are called "an array of pointers" not a "list of pointers".

Note, too, that this article is from 2010. I'm guessing that basic.get has since been rewritten to not use an O(n) implementation when an obvious O(1) implementation exists.