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) ->
   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) ->
   reverse(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:

reverse(collect_digits(List))

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

Digging Deeper into Sufficiently Smartness

previously

archives