For some time now I’ve been aware of the fact that 12 years’ professional C and C++ programming has moulded my programming thinking habits. This has been brought home particularly in the last 3 years when I’ve been doing quite advanced C++ and therefore reaching the limits of compilers and indeed the limits of C++ itself. So with that realisation, I resolved some time ago to learn more languages and broaden my current programming horizons.
I am fortunate that I learned ML before I learned C (both at university), although of course like many Brits of my generation I first learned BASIC on a BBC micro (and in fact a little 6502 assembler!). Perhaps that is why I realise the limitations of my C++ thinking in the first place. Anyway, over the last year or so I’ve been studying a bit of Lisp, and lately I’ve been studying Haskell.
Haskell reminded me of ML, or to be more accurate, reminded me of my ML course back in the day. Particularly the way it specifies function types, and although my tutorial hasn’t covered it yet, I know that curried functions are only a page or two away. Anyway, thinking back to my ML course, I remembered it really coming alive near the end when one of the exercises we had was in doing lazy list evaluation.
You are of course familiar with the Sieve of Eratosthenes. I remembered my ML exercise as using this method: i.e. lazily evaluating an infinite list of integers, then filtering out the multiples of successive list head elements. This seemed to me like a good test application for a functional language – more interesting than a factorial function (the “Hello, World!” of functional languages), and of appropriate complexity density to get a feeling for the power of the language.
So I spent some time digging in the basement and uncovered all my university lecture notes. A veritable treasure trove! But more of than another time. I found the original ML exercise (number 9 in a series of 10), which says:
Here is a definition of integer streams.
datatype stream = Item of Int * (unit->stream);
fun cons (x,xs) = Item(x, xs);
fun head (Item(i,xf)) = i;
fun tail (Item(i,xf)) = xf();
fun makeints n = cons (n, fn()=> makeints(n+1));
You can see where this is going: a stream is a tuple of (int, function to produce the rest of the stream) and repeatedly tailing the stream is repeated application of the function. Thus you get a lazily-evaluated infinite stream of integers. Then we can define a function that maps a function onto every item in the stream:
fun maps f xs = cons(f (head xs), fn()=> maps f (tail xs));
From this basis it is fairly easy to write a function that filters out all multiples of n from the stream and hence to proceed to an implementation of the Sieve of Eratosthenes.
Having refreshed my memory, I set about solving the same problem in Haskell. I needed to read a few pages ahead in the tutorial, but Haskell has two great things working for it for this problem: built-in lazy evaluation, and list comprehensions. After a bit of reading, I discovered the following:
numsFrom n = n : numsFrom (n+1)
Which produces our infinite list of integers starting from n. Because it cannot of course be completely evaluated, it’s useful to use the take function to get a given number of elements from the front:
take 10 (numsFrom 1)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
From here it was a hop and skip (via way of a list comprehension) straight to the sieve:
primes n = n : [x | x <- primes (n+1), x `mod` n /= 0]
(n is the list head, the rest of the list is made from n+1 etc with multiples of n filtered out.) And that’s it!
take 10 (primes 2)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Haskell passes the test. The Sieve of Eratosthenes in one line.