The Final Countdown

Using lists:seq/2 in Erlang, you might found some slightly unexpected although perfectly documented results. It’s nothing spectacular but I think it’s nonetheless funny.

As usual… the best images always come from NASA

Counting…

We have a Slack channel for InakaESI ex-employees. One day, Euen popped up and he just started sharing some not really surprising examples…

1> lists:seq(1, 3).
[1,2,3]
2> lists:seq(2, 3).
[2,3]
3> lists:seq(3, 3).
[3]

To be honest we didn’t find this interesting at all, until…

4> lists:seq(4, 3).
[]

Well, that is slightly weird, but not really unexpected. But then…

5> lists:seq(5, 3).
** exception error: no function clause matching lists:seq(5,3) (lists.erl, line 243)
6>
Source

What’s going on here?

Well… let’s look at the docs, shall we? According to them, lists:seq/2,3 …

returns a sequence of integers that starts with From and contains the successive results of adding Incr to the previous element, until To is reached or passed (in the latter case, To is not an element of the sequence). Incr defaults to 1.

Alright, so… translating that into our examples: lists:seq(From, 3). returns a sequence of integers that starts with From and contains the successive results of adding 1 to the previous element, until 3 is reached or passed.

That’s fine with our first 3 examples, but what about when From is greater than 3. Well, the doc continues and tells us what the failure conditions are for lists:seq/2,3

Failures:
· If To < From — Incr and Incr > 0.
· If To > From — Incr and Incr < 0.
· If Incr =:= 0 and From =/= To.

I love that last scenario, which basically tells us that we can evaluate stuff like lists:seq(1, 1, 0). to get [1]. Awesome!

Anyway, in our case, since To =:= 3 and Incr =:= 1, what we care about is that the function will fail if 3 < From — 1, which is exactly what happens for all values of From such that From > 4.

…but Why?

That’s OK, properly documented as I said and everything. But why? It seems a bit contradictory to say that the function will return a sequence of integers that starts with From and then let the function return an empty list when To == From — 1. Why not just fail when To < From and Incr > 0 (and the analogous case for Incr < 0?

On the other hand, if lists:seq/3 is going to return an empty list, why not simply return empty lists always instead of having failure scenarios, i.e. why not just return an empty list when (To < From — Incr andalso Incr > 0) orelse (To > From — Incr andalso Incr < 0)?

To figure this out, let’s go… to the code!

As you can see, validations for failure conditions are clearly stated and very specifically set outside of the recursive function that performs the list generation (i.e. seq_loop):

seq(First, Last)
when is_integer(First), is_integer(Last), First-1 =< Last ->
seq_loop(Last-First+1, Last, []).

…and…

seq(First, Last, Inc)
when is_integer(First), is_integer(Last), is_integer(Inc) ->
if
Inc > 0, First - Inc =< Last;
Inc < 0, First - Inc >= Last ->
N = (Last - First + Inc) div Inc,
seq_loop(N, Inc*(N-1)+First, Inc, []);
Inc =:= 0, First =:= Last ->
seq_loop(1, First, Inc, [])
end.

The reason for those validations lies in the wayseq_loop functions work. They’re clearly not implemented in a naïve way, i.e.…

seq_loop(Item, Last, Acc) when Item > Last -> reverse(Acc);
seq_loop(Item, Last, Acc) -> seq_loop(Item+1, Last, [Item|Acc])

They’re implemented in a more optimized fashion. Instead of counting up from First to Last, they count down from the last element on the list to 0. That way seq_loop can count 4-by-4, then 2-by-2 and more importantly, avoid a call to reverse/1 in the end.

But that recursion style changes the base cases for the recursion. While in the naïve approach above, the base case is when Item > Last, the actual implementation has 2 base cases: N == 1 and N == 0. So, in the naïve method, if you start with a From that is already larger than Last, the function will just return an empty list. With the actual seq_loop functions, if we remove the initial validation in seq, and we provide a From that would generate a negative list length (e.g. Last-From+1 < 0), seq_loop will fail with a function_clause error since it has no clause to handle negative values forN.

What the authors of seq did was just raise that same error before calling seq_loop. By doing that, they’re hiding from you (the user) the implementation details of the functions. The errors are raised from seq/2,3, not from seq_loop/3,4. I think that’s a good practice: validating user input at the API level lets you implement internal functions assuming that their input is already valid.

Now why seq/2,3 only rejects the input values that will make seq_loop fail instead of either rejecting all seemingly invalid input, i.e.(From > To andalso Incr > 0) orelse (From < To andalso Incr < 0), or returning empty lists for all those inputs…


SpawnFest

Don’t forget that on December 9–10 you can join us at SpawnFest. You’ll get to work on your favorite language, build a project, show it to some awesome judges and win important prizes!

We already have 13 teams registered, so… gather your friends, build a team a register for FREE! Or you can sign up for the find-a-teammate pool and our top-notch matching algorithm® will help you build a winning team!

For more information about the event, you can find us in the #spawnfest room at the Erlanger’s Slack