SML生成n以内素数列表遇下标越界错误求助

Hey there! Let's work through why your code is hitting that index out-of-bounds error and rewrite it to generate primes correctly using a more natural SML approach.

First, Why the Index Error Happens #

Your current code uses k to track an index into lst, with a termination condition of k > n. But here's the problem: every time you call removeMult, you're filtering out composite numbers, so lst gets shorter and shorter. Once k exceeds the length of the filtered lst minus one (since SML lists are 0-indexed), List.nth(lst, k) will throw that index error—long before k ever reaches n.

Instead of tracking indexes, we can lean into SML's functional strengths and implement the Sieve of Eratosthenes using list recursion directly, no messy indexes required.

Step 1: Define Your Helper Functions Correctly #

First, let's make sure your helper functions do exactly what we need for the sieve:

• makeLst(n): Generates a list of integers from 2 to n (since primes start at 2)
• removeMult(lst, p): Filters out all multiples of p from lst

Here's how to write these cleanly:

fun makeLst(m) = if m < 2 then [] else makeLst(m-1) @ [m];
fun removeMult(lst, p) = List.filter (fn x => x mod p <> 0) lst;

Step 2: Rewrite the Prime Generator with Sieve Logic #

The core of the sieve is recursively taking the first element of the list (which is guaranteed to be a prime), removing all its multiples from the rest of the list, and repeating the process. Here's the full working primes function:

fun primes(n) =
    let
        fun makeLst(m) = if m < 2 then [] else makeLst(m-1) @ [m];
        fun sieve([]) = []
          | sieve(p::rest) = p :: sieve(removeMult(rest, p));
    in
        if n < 2 then [] else sieve(makeLst(n))
    end;

How This Works #

1. makeLst(n) creates a list of numbers from 2 up to n (e.g., makeLst(10) gives [2,3,4,5,6,7,8,9,10]).
2. The sieve function does the heavy lifting:
   • If the input list is empty, return an empty list (our base case for recursion).
   • If the list starts with p (the smallest remaining number, which is a prime), we keep p and recursively sieve the rest of the list after removing all multiples of p.
3. Finally, we handle edge cases (like n < 2, where there are no primes) and kick off the sieve process.

Testing It #

Try running primes(10)—you should get [2,3,5,7], which is correct. For larger values like primes(30), it will return [2,3,5,7,11,13,17,19,23,29].

Why This Fixes Your Error #

By using list head recursion instead of manual index tracking, we avoid ever trying to access a position that doesn't exist in the list. This approach is far more aligned with functional programming principles in SML and eliminates the index out-of-bounds problem entirely.

内容的提问来源于stack exchange，提问作者user5504702