List Incomprehensions
I’ve already talked about this on Inaka’s blog but I thought the list of Erlang battle-stories I’m building here won’t be complete without the story of incomprehensible list comprehensions.
Introduction
This story starts with a simple recursive function that, regardless of the goal I had in mind when I wrote it, it always returned an empty list:
1> F =
1> fun F([], Acc) -> Acc
1> ; F([X|Xs], Acc) when X rem 2 == 0 ->
1> F(Xs, [X || Acc])
1> ; F([_|Xs], Acc) -> F(Xs, Acc)
1> end.
#Fun<erl_eval.36.52032458>That function includes a typo: I used the list comprehension constructor (||) when I really wanted to use a list constructor (|). The question here is then: why did that even compile in the first place?
More Examples
Now that we figured the problem was related to [X || Acc], we can isolate it and try a couple of combinations for it
2> [1 || 1].
[]
3> [something || nothing].
[]
4> [2 || []].
[]
5> [x || 1, 2, 3].
[]Looks like regardless of what you use on the right side of || you always get an empty list as the result, until…
6> [1 || true].
[1]
7> [wat || 1 == 1].
[wat]
8> [2 || true, true, true].
[2]
9> [3 || true, false, true].
[]
10> [throw(x) || false, throw(y)].
[]
11> [throw(x) || true, throw(y)].
** exception throw: y
What’s going on here?
To do things in a different way than the original article, let’s check the docs first. According to the official Erlang/OTP documentation:
List comprehensions are written with the following syntax:
[Expr || Qualifier1,...,QualifierN]Here, Expr is an arbitrary expression, and each Qualifier is either a generator or a filter.
- A generator is written as:
Pattern <- ListExpr.
ListExpr must be an expression, which evaluates to a list of terms. - A bit string generator is written as:
BitstringPattern <= BitStringExpr.
BitStringExpr must be an expression, which evaluates to a bitstring. - A filter is an expression, which evaluates to true or false.
With that in mind, it’s easy to see that our original list comprehension ([X || Acc]) is parsed as [Expr || Qualifier1], where Expr is X and Qualifier1 is Acc. And since Acc doesn’t look like Pattern <- ListExpr nor BitstringPattern <= BitStringExpr we can tell that the compiler treats it as a filter.
As you can see in the paragraphs above, Erlang impose no restrictions on how many filters or generators you must have. It just states that you must have at least one qualifier.
But the question remains: how should a list comprehension be evaluated when it has no generators?
Let’s see what the Erlang docs say about the semantics of list comprehensions:
A list comprehension returns a list, where the elements are the result of evaluating Expr for each combination of generator list elements and bit string generator elements, for which all filters are true.
In general, this statement is fine, but what happens when we do not have any generators? In that case, the meaning of “each combination of generator list elements and bit string generator elements” seems to be a little unclear.
Personally, I would’ve seen an empty list ([]) as the proper evaluation of any list comprehension without generators. But the implementors of this particular language feature had a different idea in mind. In Erlang/OTP (at least up to version 19.0) when the list comprehension has no generators the semantics are understood as follows:
A list comprehension returns a list, where the elements are the result of evaluating Expr when all filters are true.
Actually, I would’ve just opted for a much stricter syntax and required at least one generator for a list comprehension expression to be even syntactically correct. But that’s just me ;)
