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

黃耀賢 (Yau-Hsien Huang) <>
Wed Mar 30 08:56:31 CEST 2011


On Tue, Mar 29, 2011 at 4:33 PM, JohnyTex <>
 wrote:

> Anyway, here's my solution to the second problem from Project Euler
> (http://projecteuler.net/index.php?section=problems&id=2). The problem
> is to find the sum of all the even fibonacci numbers below four
> million; I thought this could be a good exercise since it would let me
> try my hand at implementing lazy sequences and working with lists.
>
> I split up the program into two modules. The first one is for handling
> lazy sequences, since I thought that would be a good way to find our
> list of primes:
>
 cut().

> %% Lazy sequence that generates fibonacci numbers
> lazyfib(A, B) -> [A | fun () -> lazyfib(B, A + B) end].
> lazyfib() -> lazyfib(0, 1).
>
>
> %% Generate all fibonacci terms that are less than 4 million and sum
> the
> %% even terms
> solve() ->
>    Fibs = seqs:takewhile(fun (X) -> X < 4000000 end, lazyfib()),
>    sum(filter(fun (X) -> X rem 2 =:= 0 end, Fibs)).
>
> Thanks in advance, and please tell me if this is not the appropriate
> forum for this kind of question! :)
>

It helps nothing but only generating a Fibonacci number sequence. The
lazyfib/2 generate a lazy
sequence and give the whole to seqs:takewhile/2, which is dedicated to the
lazy sequence.

IMHO, first I have a fib/1 function as interface with its implementation
fibonacci/4.

-module(test).
-compile(export_all).
fib(0) -> 1;
fib(1) -> 1;
fib(N) ->
    fibonacci(0, N, fib(0), fib(1)).
fibonacci(N, T, N_2, _) when N == T ->
    N_2;
fibonacci(N, _, _, _) when N < 0 ->
    false;
fibonacci(N, T, N_2, N_1) ->
    fibonacci(N + 1,  T,  N_1,  N_2 + N_1).


I'd better to use this native fib/1 function to generate the Fibonacci
number list.
In fibonacci/4 I knew two facts:
1. By calling fibonacci(N, N, N_2, N_1), I'll get any fib(N) if N_2 and N_1
are correct base
numbers.
2. For the next number in the sequence, { N, N_2, N_1 } are key variants.
For any number with
variants { N, N_2, N_1 }, it should pass { N+1, N_1, N_2 + N_1 } to its next
number.

So, I wrote fib_seq/2 as interface to generate a limited sequence of
Fibonacci numbers, which
has a lazy version of implementation fib_seq_l/4.

fib_seq(From, Limited_value) when From < 0 ->
    fib_seq(0, Limited_value);
fib_seq(From, Limited_value) ->
    fib_seq_l(From, fib(From), fib(From+1), Limited_value).
fib_seq_l(_, N_2, _, Limited_value) when N_2 > Limited_value ->
    [];
fib_seq_l(N, N_2, N_1, Limited_value) ->
    [ fibonacci(N,  N,  N_2,  N_1)
      | fun() -> fib_seq_l(N + 1,  N_1,  N_2 + N_1,  Limited_value) end ].


Now it can generate a Fibonacci number sequence limited to a maximum value
4000000.

> *test:fib_seq(0, 4000000).*
[1|#Fun<test.0.28629712>]

The result of a sequence like test:fib_seq(0, 4000000) can be exploded by
explode/1.

explode([]) ->
    [];
explode(L) when is_function(L) ->
    explode(L());
explode([H|T]) ->
    [H|explode(T)].


> *test:explode(test:fib_seq(0,4000000)).*
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,
 4181,6765,10946,17711,28657,46368,75025,121393,196418,
 317811,514229|...]

And even_seq_l takes another problem, picking all even numbers from a
maybe-with-infinite-length
list of numbers.

even_seq_l([]) ->
    [];
even_seq_l([H|T]) when H rem 2 == 0 ->
    case is_function(T) of
true ->
    [ H | fun() -> even_seq_l(T()) end ];
false ->
    [ H | fun() -> even_seq_l(T) end ]
    end;
even_seq_l([_|T]) ->
    case is_function(T) of
true ->
    fun() -> even_seq_l(T()) end;
false ->
    fun() -> even_seq_l(T) end
    end.

And then, by merging even_seq_l/1 and fib_seq/2 functions, I can get even
numbers from a limited
list of Fibonacci numbers.

even_fib_seq(From, Limited_value) ->
    even_seq_l(fib_seq(From, Limited_value)).


It's almost there.

solution_problem2() ->
    R = even_fib_seq(0, 4000000),
    io:format("Sum of ~w is ~w~n", [explode(R), sum_l(R)]).


And the result should be

> *test:solution_problem2().*
Sum of [2,8,34,144,610,2584,10946,46368,196418,832040,3524578] is 4613732
ok

I need sum_l/2 for lazy summing.

sum_l([]) ->
    0;
sum_l(L) when is_function(L) ->
    sum_l(L());
sum_l([H|T]) ->
    H + sum_l(T).


However the +/2 operator slightly break the laziness if sum_l/1 tend to
accept a big sequence.

/yau


-- 

Best Regards.

--- Y-H. H.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20110330/cde0511d/attachment.html>


More information about the erlang-questions mailing list