programming in the
twenty-first century

It's not about technology for its own sake. It's about being able to implement your ideas.

Digging Deeper into Sufficiently Smartness

(If you haven't read On Being Sufficiently Smart, go ahead and do so, otherwise this short note won't have any context.)

I frequently write Erlang code that builds a list which ends up backward, so I call lists:reverse at the very end to flip it around. This is a common idiom in functional languages.

lists:reverse is a built-in function in Erlang, meaning it's implemented in C, but for the sake of argument let's say that it's written in Erlang instead. This is super easy, so why not?

reverse(L) -> reverse(L, []).
reverse([H|T], Acc) ->
   reverse(T, [H|Acc]);
reverse([], Acc) ->

Now suppose there's another function that uses reverse at the very end, just before returning:

collect_digits(L) -> collect_digits(L, []).
collect_digits([H|T], Acc) when H >= $0, H =< $9 ->
   collect_digits(T, [H|Acc]);
collect_digits(_, Acc) ->

This function returns a list of ASCII digits that prefix a list, so collect_digits("1234.0") returns "1234". And now one more "suppose": suppose that one time we decide that we really need to process the result of collect_digits backward, so we do this:


The question is, can the compiler detect that there's a double reverse? In theory, the last reverse could be dropped from collect_digits in the generated code, and each call to collect_digits could be automatically wrapped in a call to reverse. If there ends up being two calls to reverse, then get rid of both of them, because it's just wasted effort to double-reverse a list.

With lists:reverse as a built-in, this is easy enough. But can it be deduced simply from the raw source code that reverse(reverse(List)) can be replaced with List? Is that effort easier than simply special-casing the list reversal function?

permalink June 14, 2009



twitter / mail

I'm James Hague, a recovering programmer who has been designing video games since the 1980s. Programming Without Being Obsessed With Programming and Organizational Skills Beat Algorithmic Wizardry are good starting points. For the older stuff, try the 2012 Retrospective.

Where are the comments?