Towards a third attempt

In functional programming languages such as Haskell, a technique called lazy evaluation is used as the underlying computing machinery [6]. The idea is that if one wants to compute a small initial segment of a large sequence, it is not necessary, in general, to evaluate the whole sequence. In fact, in this way one can meaningfully compute with infinite sequences. Here is an example.

    > from n = n : from (n+1)
    > from 0
      [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ctrl-C
    > take 5 (from 11)
      [11, 12, 13, 14,15]
    > take 6 (map square (from 1))
      [1, 4, 9, 16, 25, 36]

The Haskell operator ``:'' (pronounced ``cons'') takes an element x and a sequence s, producing a sequence x:s whose first term is x and whose remaining terms are those of s. For example, 3:[4,5,6]=[3,4,5,6]. Thus, from a denotational point of view, from n is the sequence of all integers starting from n. Operationally, this works more or less as follows. In order to evaluate a list expression e, the computing machinery tries to reduce the expression to the form [] (the empty sequence) or x:e'(a head-normal form). Initially, e' is left unevaluated; if, and only when, more terms of the sequence are required, e' is further reduced (to either the empty sequence or a head-normal form). Thus, if one asks for the expression from 0 to be evaluated, one gets the infinite sequence of natural numbers. In this case, the execution only stops when one explicitly interrupts it, because only finitely many states are needed to evaluate the expression. For other expressions, infinitely many states may be needed, in which case the execution is interrupted when the computer runs out of memory or the user runs out of patience, whichever happens first. But an infinite list can also be used as an intermediate step in the computation of a finite list. For example, take 5 (from 11) takes the first five elements of the infinite list of natural numbers starting from 11, and its computation successfully terminates after finitely many steps producing a finite list.

A slightly more interesting example is this (well-known) implementation of the sieve of Erasthotenes to compute the infinite list of prime numbers:

     > notdivisibleby m n = (n `mod` m) /= 0
     > sieve (p:l) = p : sieve (filter (notdivisibleby p) l) 
     > prime = sieve (from 2)
     > prime 
       [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,
       79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,
       163,167,173,179, ctrl-C

Here the filter function takes a predicate and list, and produces a list containing the elements of the given list that satisfy the predicate.