Saturday, January 23, 2010

Prime numbers

Erik Meijer has done this excellent series in functional programming which is available at Channel9.msdn.com
In one of the lectures he gives this example of generating an infinite list of prime numbers using lazy evaluation. His example was in Haskell. Here is the equivalent in F#:


let rec sieve nums = seq {
let head = Seq.head nums
yield head
let tail = Seq.skip 1 nums
let notMultipleOf n x = x % n <> 0
yield! sieve (Seq.filter (notMultipleOf head) tail)
}

let rec numbersAbove n = seq { yield n
yield! numbersAbove (n+1) }

let primes = sieve (numbersAbove 2)

No comments:

Post a Comment