Prime number sieve in Standard ML

Question

As practice, I have written a prime number sieve in Standard ML.

It works in a pretty straightforward way:

1. The list of known primes starts with just 2.
2. Starting with 3, check whether each odd integer is relatively prime to all numbers in the list of known primes (i.e. is not divisible by them)
   • If it's relatively prime, add it to the list of known primes.
   • If it's not, check the next odd integer.
3. Repeat step 2 until the list has however many primes we're looking for.
4. Reverse the list so that the primes are in ascending order.

Here's my code:

fun primes 0 = []
  | primes n =
    let
      fun relativelyPrime x = List.all (fn p => (x mod p <> 0))
      fun buildPrimes ps x =
          if length ps >= n then ps
          else if relativelyPrime x ps then buildPrimes (x::ps) (x + 2)
          else buildPrimes ps (x + 2)
    in
      rev (buildPrimes [2] 3)
    end

I'm still fairly new to Standard ML, so I doubt the above code is optimal or entirely idiomatic. Are there any improvements I could have made if I knew more about the language?

(Note: I realize that negative numbers will return [2]. I could raise an exception, but that's not the point of this question.)

Answer 1

      fun buildPrimes ps x =
          if length ps >= n then ps

Don't forget that length is expensive. It's definitely worth using an extra accumulator variable to track either the length or the number of primes left to find. I haven't done proper benchmarks, but it seems to give a speedup of a factor of 2 for input 10000.

---

I understand why you prepend newly found primes to the list and then reverse it at the end: appending the prime to the end of the list is expensive. But the other side of the argument is that the smaller primes are far more valuable for eliminating composite numbers, and in my testing replacing (x::ps) with (ps @ [x]) and ditching the rev makes a significant improvement to speed.

If performance is a high priority then you could take a hybrid approach which gives you the best of both worlds at the cost of complicating the code: have one list which is sorted in increasing order and another list which is sorted in decreasing order. Use additional accumulator variables to track their lengths. Add new primes to the front of the decreasing list, and when the decreasing list is as long as the increasing list replace them with asc @ (rev desc) and [].

---

My SML isn't at a level where I feel qualified to say what is idiomatic and what isn't, but one of the most advanced things I studied in SML at university was lazy infinite lists, and I think they have a claim to be fairly idiomatic in functional languages in general. It's not too hard to rework this sieve into a lazy infinite style. We define a type for lazy infinite lists of integers:

datatype stream = Cons of int * (unit -> stream);

where unit is the tuple of length 0, (); then a lazy list of all integers can be built with

fun integers n = Cons(n, fn () => integers (n + 1));

Filtering an infinite list is useful enough to define it outside the prime generator:

fun filter f (Cons(x,xs)) =
    if f(x) then Cons(x, fn () => filter f (xs()))
    else filter f (xs());

And then the sieve itself just builds up layers of filters:

val primes =
    let
        fun filter_multiples m = filter (fn i => i mod m <> 0)
        fun prime_extractor (Cons(p,xs)) = Cons(p, fn () => prime_extractor (filter_multiples p (xs())))
    in
        prime_extractor (integers 2)
    end;

For testing purposes, converting the first n elements to a normal list is convenient:

fun take 0 (Cons(x, xs)) = []
  | take n (Cons(x, xs)) = x :: (take (n - 1) (xs()));

For production quality this should probably be wrapped in a module, but that's at the level that I've heard of it but don't know any details.