{"id":263,"date":"2007-01-16T17:06:00","date_gmt":"2007-01-17T00:06:00","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=263"},"modified":"2007-07-29T12:42:40","modified_gmt":"2007-07-29T19:42:40","slug":"a-functional-weekend","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=263","title":{"rendered":"A Functional Weekend"},"content":{"rendered":"

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.
\n
\nI 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<\/a>.<\/lj-cut><\/p>\n

Haskell reminded me of ML<\/a>, 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<\/a> 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.<\/p>\n

You are of course familiar with the Sieve of Eratosthenes<\/a>. 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.<\/p>\n

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:<\/p>\n

Here is a definition of integer streams.<\/em><\/p>\n

datatype stream = Item of Int * (unit->stream);
\nfun cons (x,xs) = Item(x, xs);
\nfun head (Item(i,xf)) = i;
\nfun tail (Item(i,xf)) = xf();
\nfun makeints n = cons (n, fn()=> makeints(n+1));<\/em><\/p>\n

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:<\/p>\n

fun maps f xs = cons(f (head xs), fn()=> maps f (tail xs));<\/em><\/p>\n

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.<\/p>\n

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:<\/p>\n

numsFrom n = n : numsFrom (n+1)<\/em><\/p>\n

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<\/em> function to get a given number of elements from the front:<\/p>\n

take 10 (numsFrom 1)
\n<\/em>gives
\n[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]<\/em><\/p>\n

From here it was a hop and skip (via way of a list comprehension) straight to the sieve:<\/p>\n

primes n = n : [x | x <- primes (n+1), x `mod` n \/= 0]<\/em><\/p>\n

(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!<\/p>\n

take 10 (primes 2)
\n<\/em>gives
\n[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]<\/em><\/p>\n

Haskell passes the test. The Sieve of Eratosthenes in one line.<\/p>\n","protected":false},"excerpt":{"rendered":"

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…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-263","post","type-post","status-publish","format-standard","hentry","category-haskell"],"_links":{"self":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/263","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=263"}],"version-history":[{"count":0,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/263\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=263"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=263"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=263"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}