Playing with Haskell’s lazy lists
I love Haskell. I love many things about it, but one of its main attractions for me is that it is lazy. I guess I like that because I’m lazy myself.
Lazyness in Haskell means that we get infinite lists (or streams) for free - i.e. they don’t need any special handling over finite lists. Granted, other languages have infinite lists, but in Haskell any regular list has the natural potential of being infinite so we don’t need any specific syntax or constructors for them.
So, when I read about a Rutgers graduate student named Eric Rowland that recently discovered a simple prime-number generating formula, I decided to try it out in Haskell. Turns out it is extremely simple.
The generating formula is based on the sequence a(n) that you get by setting a(1) = 7 and then for n ≥ 2:
a(n) = a(n-1) + gcd(n,a(n-1))
In Haskell, running in interactive mode (GHCi), we define this by
Prelude> let a' = (1,7) : (map ( \(n,x) -> (n+1, x + (gcd (n+1) x))) a') Prelude> take 10 a' [(1,7),(2,8),(3,9),(4,10),(5,15),(6,18),(7,19),(8,20),(9,21),(10,22)] Prelude> let a = map snd a' Prelude> take 23 a [7,8,9,10,15,18,19,20,21,22,33,36,37,38,39,40,41,42,43,44,45,46,69]
Note that each element of a’ is a tuple of the index n and the value a(n). By taking differences between successive values of this sequence, you always get either the number 1 or a prime number (proving this is Rowland’s contribution).
Prelude> let d = zipWith (-) (tail a) a Prelude> take 23 d [1,1,1,5,3,1,1,1,1,11,3,1,1,1,1,1,1,1,1,1,1,23,3]
So far, so good. Now in one step we remove the 1-s by using filter and get rid of duplicates by using nub (which is defined in the List module).
Prelude> :m +List Prelude List> let primes = nub $ filter (/= 1) d Prelude List> take 23 primes [5,3,11,23,47,101,7,13,233,467,941,1889,3779,7559,15131,53,30323,60647,121403,242807,19,37,17]
Neat! The list primes is of course infinite and we could pluck the values off it as long as we like, and Haskell’s laziness will make sure values are only computed on demand. Rowland’s paper contains the details of the math.
OJ:
While this is functionality equiv (I think … I haven’t compiled it :)), I think it’s a better option than the version listed above, as I find it easier on the eyes :)
let a’ = (1 ,7) : [ (n + 1, x + (gcd (n + 1) x)) | (n, x) <- a' ]
Perhaps it’s just me, but list comprehensions tend to win the readability award when compared to lambda expressions.
Nice blog! Cheers.
24 July 2008, 4:26 amArnar:
@OJ: Ah, yes.. I agree, the list comprehension is much more readable. I guess I should have that in mind whenever I find myself writing something with the form
map (\x -> term) xs.Thanks!
24 July 2008, 10:40 amOJ:
I suffer from the same kind of thing myself mate. I’m still relatively new to Haskell, and have a lot to learn. It’s a fantastic language though.
Keep up the great work with the blog, and thanks for offering your advice on my Haskell solutions to Project Euler :) Cheers!
24 July 2008, 11:52 amJedai:
Note that nub only demands that the list element be part of the Eq typeclass. As a result it is very inefficient and a better solution must always be prefered whenever the nature of the elements allows it.
La différence de performance est énorme.
24 July 2008, 2:57 pmArnar:
@Jedai: thanks. I wonder why nub isn’t implemented like this in the first place, relying on Ord rather than Eq.
24 July 2008, 6:51 pmOJ:
Great tidbit Jedai! I’ll be adding that to the memory banks. Might even post about it to share the knowledge. :)
28 July 2008, 1:05 amA Better ‘nub’ • OJ’s rants:
[...] my TODO list, but I haven’t yet got round to it. So you can imagine my delight when I found this comment by Jedai over at hvergi.net. He’d pointed out that nub was indeed inefficient, and showed an [...]
28 July 2008, 10:17 amBookmarks about Dev:
[...] - bookmarked by 4 members originally found by christopherllc on 2008-07-24 Playing with Haskell’s lazy lists http://www.hvergi.net/2008/07/playing-with-haskells-lazy-lists/ - bookmarked by 3 members [...]
17 August 2008, 5:45 pm