Prime number lazy sequence

Question

I am new in F# and I am just wondering if is there any way to get lazy sequence of prime numbers in F#.

In Haskell I use next code:

primes :: [Integer]
primes = sieve[2..]
       where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]

In F# I can check if is the number is prime:

let isPrime (number : bigint) =
    match number with
        | _ -> seq { bigint(2) .. bigint(Math.Sqrt(float number))}
        |> Seq.exists (fun x -> if (number % x = bigint(0)) then true else false)
        |> not

But I don't know how to convert it to lazy sequence.

Answer 1

See this question for a lot of answers giving lazy prime number sequences in F#.

For a naive solution using your isPrime implementation (i.e. I'm thinking you may be interested in seeing how to go about generating a infinite sequence from a filter function in general), try this:

let primes =
    Seq.initInfinite (fun i -> i + 2) //need to skip 0 and 1 for isPrime
    |> Seq.map (fun i -> bigint(i))
    |> Seq.filter isPrime

However, you'll probably want to go about solving Project Euler Problem 3 differently by implementing a function which specifically factorizes a number rather than exhaustively dividing the number by primes and taking the largest. Though you will eventually need a prime sequence generator for problems further on.

Answer 2

If you want to mimic Haskell's laziness, you can use the LazyList type found in FSharp.PowerPack.dll. The LazyList.Cons(p,xs) is a pattern match corresponding to p:xs in Haskell. The 'Delayed' in consDelayed is necessary, because the regular LazyList.cons will be too eager and take infinitely (limited by your patience of course) long.

You might also find this question interesting. It's another Haskell prime sieve in F#.

Here's your code in F# (unfortunately rather ugly):

#r "FSharp.PowerPack.dll"

//A lazy stream of numbers, starting from x
let rec numsFrom x = LazyList.consDelayed x (fun () -> numsFrom (x+1I))

let rec sieve = function
    | LazyList.Cons(p,xs) ->
        LazyList.consDelayed p (fun () -> 
                xs |> LazyList.filter (fun x -> x%p <> 0I) |> sieve)
    | _ -> failwith "This can't happen with infinite lists"

let primes() = sieve (numsFrom 2I)

Example output in FSI:

> primes() |> Seq.take 14 |> Seq.toList;;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : System.Numerics.BigInteger list =
  [2I; 3I; 5I; 7I; 11I; 13I; 17I; 19I; 23I; 29I; 31I; 37I; 41I; 43I]