[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