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, not by call-by-value evaluation. This is like manipulating with symbols or formulae in a mathematical calculation and substituting the numerical values in an expression at the very last step. This method of evaluation results in the function primes returning a (potentially infinite, hardware limitations and the expected life span of the Solar System permitting) list of infinite numbers:

> primes
[2, 3, 5, 7, 11, 13, 17, …

For a mathematician, the above four lines of Haskell code are a revelation.

First of all, the programme (and the computer running this programme) appear to successfully manipulate with infinite sets. Secondly, the modest four lines of code simply brush aside the centuries long dispute about the actual and potential infinity and blend the apparently irreconcilable concepts together in the spirit of “internal set theory” (E. Nelson,  Internal set theory, a new approach to NSA, Bulletin of the American Mathematical Society, 83 (1977), 1165-1198; A. M.  Robert, Nonstandard Analysis. Mineola, NY: Dover Publications, 2003.): an infinite set is treated as a real object because it is given a name which is then used as a name of an actual object. On the other hand, we have access only to those elements in the set that we have already explicitly constructed. The set is like a cookies jar which contains only those cookies that we have put in it – but we can take the jar from a shelf and place it on a table regardless of how many cookies it contains.

About these ads

Responses

  1. For an interesting discussion of this program, see Melissa O’Neill’s paper “The Genuine Sieve of Eratosthenes” (DOI: 10.1017/S0956796808007004, preprint at http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf).

  2. [...] An interesting programing language noted. [...]

  3. @Hans Lundmark: Many thanks!

  4. Just a quick note on the formatting of the code example. It is incorrect to use => or ‘.

  5. my apologies, my comment was meant to make the point that the code in the example uses the incorrect ‘arrows’ in Haskell and should be replaced by a hyphen in place of the equals ‘-‘. This code would not compile in ghc.

  6. [...] On Thursday, Republic of Math thought about radical approaches to changing the math curriculum in higher education, Neverendingbooks elaborated on Manin’s comparison of the field with one element and art movements. Setting an example, Piece Of Mind shared the reasons to head the Mprime Network. On the lighter side, DataIsNature introduced its readers to the curious copyright on random digits while Mathematics under the Microscope gave one more reason why Haskell is every mathematician’s dar…. [...]

  7. Specifically, handling infinitary objects requires non-strict evaluation of which call-by-name evaluation is an example. http://en.wikipedia.org/wiki/Evaluation_strategy#Non-strict_evaluation


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

Follow

Get every new post delivered to your Inbox.

Join 83 other followers

%d bloggers like this: