Haskell综合列表动态函数：素数判别器内存优化技术问询

Let's start by looking at your original non-optimal prime checker:

isPrime :: Int -> Bool
isPrime n | n < 2 = False | otherwise = ( and [ n `mod` d /= 0 | d <- [2 .. (n-1)] ] )

First, great observation about lazy evaluation and how and short-circuits when it hits a False. Now to break down your core questions:

Does and compress the list of Trues to save memory? #

Nope, it doesn't. Here's why: Haskell lists are linked lists—each element is a separate value pointing to the rest of the list. When you generate [n mod d /= 0 | d <- [2 .. (n-1)]] for a large prime, every element in that list is True, and each one gets allocated in memory as and traverses it.

and's only job is to check elements in order: it stops at the first False, but if all are True, it has to walk through every single one. It has no logic to merge or "compress" multiple Trues into one—each element is processed individually, so all those Trues stick around in memory until the traversal finishes.

How to write a more memory-efficient function for this? #

The problem with the original code isn't just and—it's that we're generating way more elements than we need. Let's fix this with two practical approaches:

1. Cut the list short (check up to √n) #

A key mathematical fact: if a number n has a divisor greater than √n, its corresponding pair divisor will be smaller than √n. So we only need to check up to the square root of n instead of n-1. This drastically reduces the number of elements in the list:

isPrime :: Int -> Bool
isPrime n
  | n < 2     = False
  | n == 2    = True  -- Handle the only even prime separately
  | even n    = False -- Early exit for even numbers >2
  | otherwise = and [n `mod` d /= 0 | d <- [3,5..floor (sqrt (fromIntegral n))]]

We also added checks for even numbers first to skip half the possible divisors right away. This version uses way less memory because the list is orders of magnitude shorter for large primes.

2. Avoid generating a list entirely (recursive approach) #

For maximum memory efficiency, we can ditch the list comprehension altogether and use recursion to check divisors one by one. This way, we don't allocate any list elements at all—we just track the current divisor we're checking:

isPrimeRec :: Int -> Bool
isPrimeRec n
  | n < 2     = False
  | n == 2    = True
  | even n    = False
  | otherwise = checkDivisors 3
  where
    checkDivisors d
      | d*d > n   = True  -- If we've passed √n, n is prime
      | n `mod` d == 0 = False  -- Found a divisor, not prime
      | otherwise = checkDivisors (d+2)  -- Check next odd number

This recursive function uses constant memory (aside from the tiny call stack) because it doesn't build any list. It short-circuits exactly like and, but without the overhead of list elements.

Wrap-up #

To recap: and doesn't compress lists of Trues—each element stays in memory until the traversal completes. To handle large primes efficiently, either limit the number of elements you generate (by checking up to √n) or avoid generating a list entirely with a recursive approach.

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