[erlang-questions] Erlang again!

[Dave Vandervies]

Somebody claiming to be Boris M??hmer wrote:

> Well, I didn't know about zip or zipwith (still not inside the
> library), so my solution was like this:
> 
>     sub(L2,L1) ->
>         lists:reverse(sub(L2,L1,[])).
> 
>     sub([],[],List) ->
>         List;
>     sub([H2|T2],[H1|T1],List) ->
>         sub(T2,T1,[(H2-H1)|List]).
> 
> Ok, this is much longer than with zip or zipwith, but somehow this was
> much easier to "develop". Well, at the end of the documentation of
> zipwith there is almost a solution to the problem, but I wouldn't have
> found it, if zip or zipwith wasn't mentioned.
> 
> Is such a solution plain bad, or just a newbie mistake/error?

It's not bad, but there are two newbie mistakes/errors here.

Not knowing the library has already been mentioned, and it's the
lesser one; reimplementing library functions is almost always a
useful learning exercise, and reinventing it yourself before you
find it in the library gives you some insight into why it's in the
library and what you can use it for.

The bigger one is that if you build a list and then reverse it,
you're probably doing something wrong[1].  In particular, just
because you CAN write something tail-recursively doesn't mean you
SHOULD, and if the tail-recursive version ends up accumulating a
temporary that's the same size as the call stack would be that's a
pretty good sign you're not going to gain much.
(Tail recursion is a bigger win when you're accumulating into
something you can return directly or when the accumulator keeps a
constant size.)

In this case, the body-recursive version:
--------
sub([],[]) -> [];
sub([H1|T1],[H2|T2]) -> [H2-H1 | sub(T1,T2)].
--------
uses approximately the same working memory (both are linear in the
length of the list, and possibly with the same constant factor[2]),
avoids building a structure you're just going to throw away, and
is easier to read since the structure of the code matches what it's
actually doing more closely.


dave

[1] That's a "If you think you want to do this, you should consider
    alternatives first" wrong, not a "never do this" wrong.
[2] See entry 2.3 at <http://www.erlang.org/doc/efficiency_guide/myths.html>

-- 
Dave Vandervies
dj3vande@REDACTED / dj3vande@REDACTED

Plan your future!  Make God laugh!
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 195 bytes
Desc: not available
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20100724/03586a28/attachment.bin>