3
\$\begingroup\$

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.)

\$\endgroup\$
1
\$\begingroup\$
      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.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is exactly the sort of answer I was looking for. Thank you. I wasn't sure if length was expensive or if it was shortcut behind the scenes by keeping track of the length internally, the way most languages do it. So I decided to use the simpler approach. \$\endgroup\$ – James Jensen Jul 20 '18 at 3:10
  • \$\begingroup\$ @JamesJensen: Lists in SML are linked lists, so there's no keeping track of the length. Many languages use some kind of array-list hybrid, i.e. an array that also has a list interface, so you get O(1) index and length, but extending the list can cause a fully array copy. \$\endgroup\$ – Simon Shine Sep 6 '18 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.