[erlang-questions] Re: Newbie Erlang programmer looking for feedback! :)

Richard O'Keefe ok@REDACTED
Wed Mar 30 02:38:02 CEST 2011


Let's start with a Haskell version.

euler2 = (sum . filter even . takeWhile (<= 4000000)) fibs
  where fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

On 29/03/2011, at 9:33 PM, JohnyTex wrote:

A "lazy" fib generator, with "lazy" in scare quotes because
repeated evaluation will redo work, a version of
lists:takewhile/2 adapted to "lazy" lists, his own copies
of lists:sum/1 and lists:filter/2, and something rather
like the Haskell version.

There are many ways we can judge a piece of code.
"Does it do the job?"  Yes, it does.
"Is it easy to see that it does the job?"  Yes, it is.
"Does it use the language idiomatically?"  No.

JohnyTex's Erlang code is basically an adaptation to Erlang
of an approach which is idiomatic in Haskell.  It has as its
core idea "store a data structure representing all the
Fibonacci numbers".

Here's an Erlang version:

euler2() ->
    fib_sum(1, 1, 4000000, 0).

fib_sum(F0, F1, Limit, Sum) ->
    F2 = F0 + F1,
    if F2 > Limit -> Sum
     ; true       -> fib_sum(F1, F2, Limit,
                             case F2 band 1 of 0 -> Sum+F2 ; 1 -> Sum end)
    end.

It has as its core idea "iterate over a prefix of the Fibonacci numbers".
It allocates no storage and is tail recursive.
It is, in fact, the *direct* equivalent of

#include <stdio.h>

int main(void) {
    int const Limit = 4000000;
    int Sum;
    int F0, F1, F2;

    Sum = 0;
    for (F0 = F1 = 1; (F2 = F1 + F0) <= Limit; F0 = F1, F1 = F2)
        if ((F2 & 1) == 0) Sum += F2;
    printf("%d\n", Sum);
    return 0;
}

In the C version and my Erlang version, "Is it easy to see that it
does the job" gets the defensive answer "well, it may not be
OBVIOUS, but ..." which really amounts to "no".

Can we perhaps compromise?

fold_fibs(Limit, Initial, Combiner) ->
    fold_fibs(0, 1, Limit, Initial, Combiner).

fold_fibs(_, F1, Limit, State, _) when F1 > Limit ->
    State;
fold_fibs(F0, F1, Limit, State, Combiner) ->
    fold_fibs(F1, F0+F1, Limit, Combiner(State,F1), Combiner).

add_if_even(X, Y) when Y band 1 =:= 0 -> X+Y;
add_if_even(X, _) -> X.

euler2() ->
    fold_fibs(4000000, 0, fun add_if_even/2).

This factorises the problem as "folding over a prefix of the
Fibonacci numbers" and "summing even numbers".  It isn't as
immediately obvious as the Haskell version, but it should be
easier to understand than the "bare bones" version.
clear



More information about the erlang-questions mailing list