Newest Entry
Complete Archives
I'm a recovering programmer who has been designing video games since the 1980s, doing things that seem baroquely hardcore in retrospect, like writing Super Nintendo games entirely in assembly language. These days I use whatever tools are the most fun and give me the biggest advantage.
james.hague @ gmail.com
Where are the comments?
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?