Here is the canonical implementation of Fibonacci series in Haskell. The lazy evaluation semantics of Haskell is used to build the Fibonacci series as a lazy list. I thought about implementing lazy lists in languages that don’t have lazy evaluation semantics.
The above code uses the zipWith function, which operates on lazy lists. I didn’t want to implement that yet, so I wrote the following simpler implementation in Haskell, which still result in lazy lists. The first one, “from”, is just an infinite sequence of integers starting at n.
The second one is the infinite Fibonacci series, but without using zipWith.
fibs = fibs_helper 0 1
Lazy Lists in Python
The first language I decided to try was Python. The representation for the lazy list I chose was a pair of objects. The first, called “first”, is the first element in the list. The second, called “rest”, is a function, that returns the rest of the lazy list. The “first” of the “rest” is the second element, and so on. I just decided to put the pair of objects in a dictionary. So if I had a lazy list ‘L’, L['first'] would give me the first element, and L['rest']() would give me the rest of the lazy list. The first order of business was to write the “Take” function, that returns the first ‘n’ elements of a lazy list as a regular list. Here is the recursive implementation of “Take”. Take(0, l) is the empty list. Take(n, l) is the first element of l (l['first']) appended with Take(n-1, l['rest']()). Easy enough.
if (n==0):
return []
else:
return [l['first']] + Take(n-1, l['rest']())
Now, we are ready to implement the ‘from’ lazy list. Obviously, the first element of from(n) is ‘n’. What about the ‘rest’ part? Remember, the ‘rest’ is supposed to be a function that should return the lazy list corresponding to the rest of the list. We know the rest of the list is just From(n+1). So we just create an anonymous function (lambda) and set ‘rest’ to that anonymous function. The key observation here is that the lambda is capturing n+1. So when From(n)['rest'] is called, it knows to return From(n+1).
return {'first':n,
'rest': lambda: From(n+1) }
The implementation of fibs is as follows:
return {'first':m,
'rest': lambda: fibs_helper(n, m+n)}
fibs=fibs_helper(0, 1)
Since an element in a Fibonacci sequence depends on the previous two elements in the sequence, I make the helper function take 2 arguments, namely two consecutive elements in the sequence. The function fibs_helper(m, n) returns the lazy list starting at m. Again, the ‘first’ is m. The ‘rest’ is recursively defined by calling fibs_helper with n and n+m, as they are the next two elements in the sequence. Go ahead, try out
Take(20, fibs)
Lazy Lists in R
Next, I tried to do it in R, that also has strict evaluation semantics. This is pretty straightforward, and looks identical to the Python implementation.
if (n == 0) c()
else c(l$first, take(n-1, l$rest()))
}
list(first=n, rest=function() { from(n+1) })
}
list(first=m, rest=function() { fibs_helper(n, m+n) })
}
fibs <- fibs_helper(0, 1)
Lazy Lists in C++
Next, I tried to implement it in C++. First, the “take” function template is shown below. It take a lazy list, and as long as that class has a “first” member and a “rest” method, the “take” function is happy. It just recursively calls itself and returns a std::vector
using namespace std;
template<typename F>
vector<int> take(int n, F f)
{
if (n==0)
return vector<int>();
else {
vector<int> retval;
retval.push_back(f.first);
vector<int> temp = take(n-1, f.rest());
std::copy(temp.begin(), temp.end(),
std::inserter(retval, retval.end()));
return retval;
}
}
Now, let’s look at the “from” lazy list. It is a class with the “first” member, which is set in the constructor. The “rest” is a method that returns a new object of type “from”, but constructed with n+1. Simple enough, again.
int first;
from(int n) : first(n) {}
from rest() { return from(first+1); }
};
fibs is similar in spirit, but since we know the infinite list always begins at 0, I just declared an object called fibs, constructed with (0,1).
int m, n;
int first;
fibs(int _m, int _n) : m(_m), n(_n), first(_m) {}
fibs rest() { return fibs(n, m+n); }
} fibs(0, 1);
Here is the main program that calls “take” on fibs, to get the first 10 elements, and prints them out.
{
vector<int> t = take(10, fibs);
for (unsigned i=0, e=t.size(); i!=e; ++i)
cout << t[i] << "\n";
return 0;
}
Lazy Lists in C++0x
Or C++11, as it is known now. I just changed the implementation of “rest”. Instead of a being a class method, it is just a class member of type std::function<from()>, (or std::function<fibs()>). I set it in the constructor to a lambda expression, just like the Python or R implementation.
int first;
function<from()> rest;
from(int n) : first(n), rest([=] ()->from {return from(n+1);}) {}
};
struct fibs {
int first;
function<fibs()> rest;
fibs(int m, int n) : first(m), rest([=] ()->fibs {return fibs(n, m+n);}) {}
} fibs(0, 1);
I don’t understand why your Python example isn’t simply a generator.
Alternative Python approach using generators:
from itertools import islice
def From(n):
while True:
yield n
n += 1
def fibs():
x, y = 0, 1
while True:
yield x
x, y = y, x+y
def take(n, iterable):
return list(islice(iterable, n))
print(take(10, From(42)))
print(take(20, fibs()))
Rather than using list boxing and append, your original Haskell could be more simply expressed as:
from n = n : from (n+1)
Though having this lazy in the list, yet strict in the accumulator, would be more sensible:
from !n = n : from (n+1)
Why not use a Python generator?
Thanks Don, for the better Haskell way, and others for pointing out Python generators. I wanted to keep the implementation uniform between Python, R, and C++. Yes, Python yield is definitely more natural.
def Take(n,l)
return [] if n==0
return [l['first']]+Take(n-1,l['rest'].call)
end
def From(n)
{‘first’=>n,’rest’=>lambda{From(n+1)}}
end
t=From(1)
puts Take(50,t).inspect
the codes wrote with Ruby! almost the same with Python