Posted: Mar 20, 2012 6:45 pm
by epepke
VazScep wrote:1, 1, 2, 3, 5, 8, 13, ...
1, 2, 3, 5, 8, 13, 21, ...

Now if you apply addition vertically, you obviously get the Fibonacci sequence with two elements chopped off the front. In other words:

Code: Select all
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Note that the way graph reduction is performed in a lazy language means that evaluation here has the same complexity as the iterative solution.

None of the LISPs available at the time had even proper tail recursion, let alone lazy evaluation.

Is there really just one LISP? I read a series of early articles in the History of Programming Languages on this, and my understanding was that there were many dialects around for decades before CL.

Yes, there were many dialects, but there is commonality between the implementation philosophies of all of them.