Learning F# - printing prime numbers

Question

Yesterday I started looking at F# during some spare time. I thought I would start with the standard problem of printing out all the prime numbers up to 100. Heres what I came up with...

#light
open System

let mutable divisable = false
let mutable j = 2

for i = 2 to 100 do
    j <- 2
    while j < i do
        if i % j = 0 then divisable <- true
        j <- j + 1

    if divisable = false then Console.WriteLine(i)
    divisable <- false

The thing is I feel like I have approached this from a C/C# perspective and not embraced the true functional language aspect.

I was wondering what other people could come up with - and whether anyone has any tips/pointers/suggestions. I feel good F# content is hard to come by on the web at the moment, and the last functional language I touched was HOPE about 5 years ago in university.

Answer 1

Simple but inefficient suggestion:

• Create a function to test whether a single number is prime
• Create a list for numbers from 2 to 100
• Filter the list by the function
• Compose the result with another function to print out the results

To make this efficient you really want to test for a number being prime by checking whether or not it's divisible by any lower primes, which will require memoisation. Probably best to wait until you've got the simple version working first :)

Let me know if that's not enough of a hint and I'll come up with a full example - thought it may not be until tonight...

Answer 2

HubFs (which is usually good for F# content) has an example which leverages a lot of F# functionality.

The focus of the article is on parallelising this operation across multiple cores but the example is instructive as to how to think 'functionally'.

Answer 3

Using a Sieve function like Eratosthenes is a good way to go. Functional languages work really well with lists, so I would start with that in mind for struture.

On another note, functional languages work well constructed out of functions (heh). For a functional language "feel" I would build a Sieve function and then call it to print out the primes. You could even split it up--one function builds the list and does all the work and one goes through and does all the printing, neatly separating functionality.

There's a couple of interesting versions here. And there are well known implementations in other similar languages. Here's one in OCAML that beats one in C.

Answer 4

Here is a simple implementation of the Sieve of Eratosthenes in F#:

let rec sieve = function
    | (p::xs) -> p :: sieve [ for x in xs do if x % p > 0 then yield x ]
    | []      -> []

let primes = sieve [2..50]
printfn "%A" primes  // [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]

This implementation won't work for very large lists but it illustrates the elegance of a functional solution.

Answer 5

You definitely do not want to learn from this example, but I wrote an F# implementation of a NewSqueak sieve based on message passing:

type 'a seqMsg =   
    | Die   
    | Next of AsyncReplyChannel<'a>   

type primes() =   
    let counter(init) =   
        MailboxProcessor.Start(fun inbox ->   
            let rec loop n =   
                async { let! msg = inbox.Receive()   
                        match msg with   
                        | Die -> return ()   
                        | Next(reply) ->   
                            reply.Reply(n)   
                            return! loop(n + 1) }   
            loop init)   

    let filter(c : MailboxProcessor<'a seqMsg>, pred) =   
        MailboxProcessor.Start(fun inbox ->   
            let rec loop() =   
                async {   
                    let! msg = inbox.Receive()   
                    match msg with   
                    | Die ->   
                        c.Post(Die)   
                        return()   
                    | Next(reply) ->   
                        let rec filter' n =   
                            if pred n then async { return n }   
                            else  
                                async {let! m = c.AsyncPostAndReply(Next)   
                                       return! filter' m }   
                        let! testItem = c.AsyncPostAndReply(Next)   
                        let! filteredItem = filter' testItem   
                        reply.Reply(filteredItem)   
                        return! loop()   
                }   
            loop()   
        )   

    let processor = MailboxProcessor.Start(fun inbox ->   
        let rec loop (oldFilter : MailboxProcessor<int seqMsg>) prime =   
            async {   
                let! msg = inbox.Receive()   
                match msg with   
                | Die ->   
                    oldFilter.Post(Die)   
                    return()   
                | Next(reply) ->   
                    reply.Reply(prime)   
                    let newFilter = filter(oldFilter, (fun x -> x % prime <> 0))   
                    let! newPrime = oldFilter.AsyncPostAndReply(Next)   
                    return! loop newFilter newPrime   
            }   
        loop (counter(3)) 2)   

    member this.Next() = processor.PostAndReply( (fun reply -> Next(reply)), timeout = 2000)

    interface System.IDisposable with
        member this.Dispose() = processor.Post(Die)

    static member upto max =   
        [ use p = new primes()
          let lastPrime = ref (p.Next())
          while !lastPrime <= max do
            yield !lastPrime
            lastPrime := p.Next() ]

Does it work?

> let p = new primes();;

val p : primes

> p.Next();;
val it : int = 2
> p.Next();;
val it : int = 3
> p.Next();;
val it : int = 5
> p.Next();;
val it : int = 7
> p.Next();;
val it : int = 11
> p.Next();;
val it : int = 13
> p.Next();;
val it : int = 17
> primes.upto 100;;
val it : int list
= [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
   73; 79; 83; 89; 97]

Sweet! :)

Answer 6

Here is my old post at HubFS about using recursive seq's to implement prime number generator.

For case you want fast implementation, there is nice OCaml code by Markus Mottl

P.S. if you want to iterate prime number up to 10^20 you really want to port primegen by D. J. Bernstein to F#/OCaml :)