2

I am very new to SML code and I am trying to make a function that returns a list of all prime numbers up to the number that is given by the user. I have most of the functions working except I keep getting an unbound variable or constructor error on my number, index, and lst variables. The code should use two helper functions to run through two indexs and multiply them getting non prime numbers out of the list. Here is my code:


fun removeMult (lst,n) = if null lst then lst else if hd lst mod n = 0 then removeMult(tl lst, n) else (hd lst) :: removeMult(tl lst, n);

fun helpertwo(lst, ind : int, n : int, indtwo : int) = if indtwo = n then lst else helpertwo(removeMult(lst , ind*indtwo),ind,n,indtwo+1);

fun test(lst,number,index) = 
if 
 number = index 
then 
 lst 
else
 helpertwo(lst, index, number, 2);
 test(lst,number,(index+1));

fun primes (n : int) = 
if 
 (n <= 1)
then
 []
else
  makelist(n);
  removeMult(lst , 1);
  test(lst, n , 2);
Jack Van Well
  • 43
  • 6
  • You need to use the results that your functions produce. Also, removing all multiples of 1 will not leave you with many "prime" numbers. – molbdnilo Jan 19 '20 at 14:52
  • Thank you @molbdnilo I knew about the multiples of one, that is why the starting index for both the functions is 2. I am trying to figure out how to set variables atm since I believe that is the problem I am running into. – Jack Van Well Jan 19 '20 at 19:42
  • You need to learn how to program without assignment and sequencing. – molbdnilo Jan 20 '20 at 15:49

2 Answers2

2

Reindenting the code gives something like this:

fun test(lst,number,index) = 
    if 
    number = index 
    then 
    lst 
    else
    helpertwo(lst, index, number, 2);
test(lst,number,(index+1));

fun primes (n : int) = 
    if 
    (n <= 1)
    then
    []
    else
    makelist(n);
removeMult(lst , 1);
test(lst, n , 2);

Some of the expressions are not part of the functions at all, which is why the parameters are not in scope. You can actually have multiple expressions in an else like this:

    else
    (helpertwo(lst, index, number, 2);
     test(lst,number,(index+1)))

But this will not work in your case because helpertwo does not have a side effect, so the real fix will be to use the result of helpertwo in some way.

Florian Weimer
  • 32,022
  • 3
  • 48
  • 92
  • Thank you for the help. I am have made a lot of the changes to my code and thanks to you I will probably be able to finish before it is due today :) I wish I could give you the uparrow but it says that I need 15 reputation before I can do that. – Jack Van Well Jan 19 '20 at 19:40
  • @Simon'ReinstateMonica'Shine Thank you :) – Jack Van Well Jan 21 '20 at 20:29
1

Here is an alternative way to generate primes using a sieve.

It is not particularly efficient, but it demonstrates lazy streams.

A stream is kind of like a list, except the tail is represented with a function that hasn't been evaluated. The particular definition of a stream below doesn't have a way to represent "end of stream", which strict lists necessarily have to. But since the primes are infinite, a stream that holds them can conceptually be, too.

datatype 'a stream = Cons of 'a * (unit -> 'a stream)

The primes are a subset of the natural numbers,

fun nats i =
  Cons (i, fn () => nats (i+1))

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

- take 10 (nats 0);
> val it = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] : int list

As for picking the primes using a sieve, see the animation of Sieve of Eratosthenes (Wikipedia): We pick the first element (starting from 2) and cross out subsequent multiples (4, 6, 8, ...). We pick the next element (being 3) and cross out subsequent multiples (6, 9, 12, ...). We pick the next element (5, since 4 is crossed out) and cross out subsequent multiples (10, 15, 20, ...), and so on.

A recursive solution using lazy streams might then look like

fun sieve (Cons (n, stream)) =
  Cons (n, fn () => sieve (remove_multiples n (stream ())))

and remove_multiples i =
  filter (fn n => n mod i <> 0)

and filter p (Cons (x, stream)) =
  if p x
  then Cons (x, fn () => filter p (stream ()))
  else filter p (stream ())

Here sieve is a recursive, lazy definition because it calls itself inside an fn () => ... which delays computation. It progressively filters out more multiples because it doesn't just call itself with a stream that has one element removed, but a stream that has a multitude of elements removed upon each recursive call.

You can take the first 10 primes:

fun primes n =
  take n (sieve (nats 2))

- primes 10;
> val it = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] : int list

Or you can take the first primes for which a predicate holds:

fun takeWhile p (Cons (x, stream)) =
  if p x then x :: takeWhile p (stream ()) else []

fun primesUpto n =
  takeWhile (fn p => p <= n) (sieve (nats 2))

- primesUpto 100;
> val it =
    [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] : int list

If you'd like a more efficient but still functional and lazy strategy, have a look at the wheel sieve.

sshine
  • 15,635
  • 1
  • 41
  • 66