Posted by: Alexandre Borovik | May 12, 2011  Infinity in Haskell
Among the huge variety of programming languages Haskell is
interesting because of its cult status and proselytising zeal of
its fans. An example like the one below is the best explanation
why this has happened. These four lines are an implementation of
the Sieve of Eratosthenes, a classical algorithm for listing
prime numbers (G. Hutton,  Programming in Haskell. Cambridge:
Cambridge University Press, 2007):  > primes :: [Int] > primes =
sieve [2..] > sieve :: [Int] => [Int] > sieve (p : xs) = p :
sieve [x | x <= xs, x `mod` p ≠ 0]  What happening here is that
function sieve is applied to the infinite list   [2..] = [2, 3,
4, 5, 6, 7,...].  The function sieve takes as argument a list of
integers and returns a list of integers; it accepts the first
number p being prime and then calls itself recursively with a
new list obtained by filtering out all multiples of p from the
list. In Haskell, expressions are evaluated using call-by-name
evaluation, n