<meta http-equiv="content-type" content="text/html; charset=utf-8"><div class="gmail_quote">On Tue, Mar 29, 2011 at 4:33 PM, JohnyTex <span dir="ltr"><<a href="mailto:ekeroth.christoffer@gmail.com">ekeroth.christoffer@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
Anyway, here's my solution to the second problem from Project Euler<br>(<a href="http://projecteuler.net/index.php?section=problems&id=2" target="_blank">http://projecteuler.net/index.php?section=problems&id=2</a>). The problem<br>
is to find the sum of all the even fibonacci numbers below four<br>million; I thought this could be a good exercise since it would let me<br>try my hand at implementing lazy sequences and working with lists.<br><br>I split up the program into two modules. The first one is for handling<br>
lazy sequences, since I thought that would be a good way to find our<br>list of primes:<br></blockquote><div> <font class="Apple-style-span" size="1">cut().</font></div><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
%% Lazy sequence that generates fibonacci numbers<br>lazyfib(A, B) -> [A | fun () -> lazyfib(B, A + B) end].<br>lazyfib() -> lazyfib(0, 1).<br><br><br>%% Generate all fibonacci terms that are less than 4 million and sum<br>
the<br>%% even terms<br>solve() -><br>   Fibs = seqs:takewhile(fun (X) -> X < 4000000 end, lazyfib()),<br>   sum(filter(fun (X) -> X rem 2 =:= 0 end, Fibs)).<br><br>Thanks in advance, and please tell me if this is not the appropriate<br>
forum for this kind of question! :)<br></blockquote></div><div><br></div>It helps nothing but only generating a Fibonacci number sequence. The lazyfib/2 generate a lazy<div>sequence and give the whole to seqs:takewhile/2, which is dedicated to the lazy sequence.<div>
<br></div><div>IMHO, first I have a fib/1 function as interface with its implementation fibonacci/4.</div><div><br></div><div><blockquote>-module(test).<br>-compile(export_all).<br>fib(0) -> 1;<br>fib(1) -> 1;<br>fib(N) -><br>
    fibonacci(0, N, fib(0), fib(1)).<br>fibonacci(N, T, N_2, _) when N == T -><br>    N_2;<br>fibonacci(N, _, _, _) when N < 0 -><br>    false;<br>fibonacci(N, T, N_2, N_1) -><br>    fibonacci(N + 1,  T,  N_1,  N_2 + N_1).</blockquote>
<div><br></div></div><div>I'd better to use this native fib/1 function to generate the Fibonacci number list.</div><div>In fibonacci/4 I knew two facts:</div><div>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</div>
<div>numbers.</div><div>2. For the next number in the sequence, { N, N_2, N_1 } are key variants. For any number with</div><div>variants { N, N_2, N_1 }, it should pass { N+1, N_1, N_2 + N_1 } to its next number.</div><div>
<br></div><div>So, I wrote fib_seq/2 as interface to generate a limited sequence of Fibonacci numbers, which</div><div>has a lazy version of implementation fib_seq_l/4.</div><div><br></div><div><div><blockquote>fib_seq(From, Limited_value) when From < 0 -><br>
    fib_seq(0, Limited_value);<br>fib_seq(From, Limited_value) -><br>    fib_seq_l(From, fib(From), fib(From+1), Limited_value).<br>fib_seq_l(_, N_2, _, Limited_value) when N_2 > Limited_value -><br>    [];<br>fib_seq_l(N, N_2, N_1, Limited_value) -><br>
    [ fibonacci(N,  N,  N_2,  N_1)<br>      | fun() -> fib_seq_l(N + 1,  N_1,  N_2 + N_1,  Limited_value) end ].</blockquote></div></div><div><br></div><div>Now it can generate a Fibonacci number sequence limited to a maximum value 4000000.</div>
<div><br></div><div><div>> <b>test:fib_seq(0, 4000000).</b></div><div>[1|#Fun<test.0.28629712>]</div></div><div><br></div><div>The result of a sequence like test:fib_seq(0, 4000000) can be exploded by explode/1.</div>
<div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><div><div>explode([]) -></div></div></div><div><div><div>    [];</div></div></div><div><div><div>
explode(L) when is_function(L) -></div></div></div><div><div><div>    explode(L());</div></div></div><div><div><div>explode([H|T]) -></div></div></div><div><div><div>    [H|explode(T)].</div></div></div></blockquote>
<div><div><div><br></div><div><div>> <b>test:explode(test:fib_seq(0,4000000)).</b></div><div>[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,</div><div> 4181,6765,10946,17711,28657,46368,75025,121393,196418,</div>
<div> 317811,514229|...]</div></div><div><br></div></div></div><div>And even_seq_l takes another problem, picking all even numbers from a maybe-with-infinite-length</div><div>list of numbers.</div><div><br></div><div><div>
even_seq_l([]) -></div><div>    [];</div><div>even_seq_l([H|T]) when H rem 2 == 0 -></div><div>    case is_function(T) of</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>true -></div><div><span class="Apple-tab-span" style="white-space:pre">   </span>    [ H | fun() -> even_seq_l(T()) end ];</div>
<div><span class="Apple-tab-span" style="white-space:pre">      </span>false -></div><div><span class="Apple-tab-span" style="white-space:pre">  </span>    [ H | fun() -> even_seq_l(T) end ]</div><div>    end;</div><div>even_seq_l([_|T]) -></div>
<div>    case is_function(T) of</div><div><span class="Apple-tab-span" style="white-space:pre">  </span>true -></div><div><span class="Apple-tab-span" style="white-space:pre">   </span>    fun() -> even_seq_l(T()) end;</div>
<div><span class="Apple-tab-span" style="white-space:pre">      </span>false -></div><div><span class="Apple-tab-span" style="white-space:pre">  </span>    fun() -> even_seq_l(T) end</div><div>    end.</div></div><div><br>
</div><div>And then, by merging even_seq_l/1 and fib_seq/2 functions, I can get even numbers from a limited</div><div>list of Fibonacci numbers.</div><div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;">
<div><div>even_fib_seq(From, Limited_value) -></div></div><div><div>    even_seq_l(fib_seq(From, Limited_value)).</div></div></blockquote><div><br></div><div>It's almost there. </div><div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;">
<div><div>solution_problem2() -></div></div><div><div>    R = even_fib_seq(0, 4000000),</div></div><div><div>    io:format("Sum of ~w is ~w~n", [explode(R), sum_l(R)]).</div></div></blockquote><div><br></div>
<div>And the result should be</div><div><br></div><div><meta http-equiv="content-type" content="text/html; charset=utf-8"><div><div>> <b>test:solution_problem2().</b></div><div>Sum of [2,8,34,144,610,2584,10946,46368,196418,832040,3524578] is 4613732</div>
<div>ok</div></div><div><br></div></div><div>I need sum_l/2 for lazy summing.</div><div><br></div><blockquote class="webkit-indent-blockquote" style="margin: 0 0 0 40px; border: none; padding: 0px;"><div><div>sum_l([]) -></div>
</div><div><div>    0;</div></div><div><div>sum_l(L) when is_function(L) -></div></div><div><div>    sum_l(L());</div></div><div><div>sum_l([H|T]) -></div></div><div><div>    H + sum_l(T).</div></div></blockquote><div>
<div><br></div></div><div>However the +/2 operator slightly break the laziness if sum_l/1 tend to accept a big sequence.</div><div><br></div><div><div>/yau</div></div><div><br></div><div><br></div><div>-- <br><div><br></div>
Best Regards.<div><br></div><div>--- Y-H. H.</div><div><br></div><br>
</div></div>