ERLANG, infinite Fibonacci list using zipWith

Question

I have a task with infinite lists.

I have to write a zipWith/3 for infinite lists - done

I have to use this zipWith/3 to create an infinite list of fibonacci numbers with fib/0 - problem

I have to write fibs(N) taking the first N elements from fib() - done

This is what I have so far:

-module(zipWith).
-export([take/2, zipWith/3, fib/0]).

take(0, _)         -> [];
take(N, [H|LazyT]) -> [H | take(N-1, LazyT())].

zipWith(F, [H1|L1], [H2|L2]) -> [F(H1, H2) | fun() -> zipWith(F, L1(),   L2()) end].

fib() -> ...
fib(L) -> zipWith(fun(X,Y) -> X + Y end, L(), tl(L())).

fibs(N) -> take(N, fib()).

I know fib/1 should look like this (I am pretty sure - correct me, if I am mistaken). Taking the list itself and the list without the head. So in case of [0,1,...] zipWith(add,[0,1,...],[1,...]) results in adding the last two numbers. But whatever I try as the beginning to this fib()->... results in errors. I want to express it somehow like this: fib() -> fib([[0,1] ++ fun() -> ... end]...)

I somehow wanted to start fib/1 with [0,1,fun()...] but do not get how to let the list begin.

Thanks in advance for advice

Answer 1

I don't understand how are you going to use zipwith here. However, I came up with the following solution:

map(_, []) -> [];
map(F, [H | T]) -> [F(H) | fun() -> map(F, T()) end].

fib1(X, Y) -> [{X, Y} | fun() -> fib1(Y, X+Y) end].

fib() -> map(fun({_X, Y}) -> Y end, fib1(1,1)).

The idea is to build some element and then pass the context for the next number.

Actually I don't think this approach implement true laziness as you have to reevaluate all the values every time you go through the list.

UPDATE

If you rally want to implement this through the zipWith, you can play around the fact that every next element of the sequence is formed as a sum of previous one and the current one.

So you can take a list of elements, and a list of elements shifted by one, and form every next element as a sum of elemetns in those lists.

You will need some few first elemetns to bootstrap. You just apply the knowledge of first two elements

As you can see, by the time of calculating 3rd element you have to know 2 first, when calculating 4th element, you have to know 2rd and 3rd, but you already calculated 3rd.

%% this eveluates the lazy list and just returns normal one
e(L) when is_list(L) -> L; 
e(LazyL) when is_function(LazyL, 0) -> LazyL().

take(0, _)         -> [];
take(N, [H|LazyT]) -> [H | take(N-1, e(LazyT))].

drop(0, T)         -> e(T);
drop(N, [_|LazyT]) -> drop(N-1, e(LazyT)).

zipWith(F, [H1|L1], [H2|L2]) -> [F(H1, H2) | fun() -> zipWith(F, e(L1),   e(L2)) end].

fib() -> [1, 1 | fun() -> zipWith(fun(X,Y) -> X + Y end, fib(), drop(1, fib())) end ].

fibs(N) -> take(N, fib()).

Last notes

1. Never write like this in real life.
2. More interesting task of this kind is to implement Sieve of Eratosthenes. The latter task is not so artificial and lazy soultion of this sort is really elegant for it