Recursion with accumulators that are not reversed - is it possible?

Question

I've been playing with Haskell a fair amount lately, and I came up with this function to find the nth prime:

nthPrime 1 = 2
nthPrime 2 = 3
nthPrime n = aux [2, 3] 3 5 n
  where
    aux knownPrimes currentNth suspect soughtNth =
      let currentIsPrime = foldl (\l n -> l && suspect `mod` n /= 0) 
                                 True knownPrimes
      in case (currentIsPrime, soughtNth == currentNth) of
        (True, True) -> suspect
        (True, False) -> aux (suspect:knownPrimes) (currentNth + 1) 
                             (suspect + 2) soughtNth
        _ -> aux knownPrimes currentNth (suspect + 2) soughtNth

My question is, is there a way to have an accumulative parameter (in this case knownPrimes) that is not reversed (as occurs when passing (suspect:knownPrimes))?

I have tried using knownPrimes ++ [suspect] but this seems inefficient as well.

My hope is that if I can pass the known primes in order then I can shortcut some of the primality checks further.

Answer 1

In Haskell, if you are using an accumulator to build a list, but end up having to reverse it, it is often the case that it is better to drop the accumulator and instead produce the list lazily as the result of your computation.

If you apply this kind of thinking to searching for primes, and take full advantage of laziness, you end up with a well-known technique of producing an infinite list of all the primes. If we refactor your code as little as possible to use this technique, we get something like:

allPrimes = [2, 3] ++ aux 5
  where
    aux suspect =
      let currentIsPrime = foldl (\l n -> l && suspect `mod` n /= 0) True
                               $ takeWhile (\n -> n*n <= suspect) allPrimes
      in case currentIsPrime of
        True -> suspect : aux (suspect + 2)
        False -> aux (suspect + 2)

nthPrime n = allPrimes !! (n-1)

I have removed now unnecessary parameters and changed the code from accumulating into lazily producing, and to use its own result as the source of prime divisors to test (this is called "tying the knot"). Other than that, the only change here is to add a takeWhile check: since the list we are testing divisors from is defined in terms of itself, and is infinite to boot, we need to know where on the list to stop checking for divisors so that we don't get a truly infinite recursion.

Apart from this, there is an inefficiency in this code:

foldl (\l n -> l && suspect `mod` n /= 0) True

is not a good way for checking whether there are no divisors in a list, because as written, it won't stop once a divisor has been found, even though && itself is shortcutting (stopping as soon as its first argument is found to be False).

To allow proper shortcutting, a foldr could be used instead:

foldr (\n r -> suspect `mod` n /= 0 && r) True

Or, even better, use the predefined function all:

all (\n -> suspect `mod` n /= 0)

Using my remarks

This is how it would look like if you use all and refactor it a bit:

allPrimes :: [Integer]
allPrimes = 2 : 3 : aux 5
  where
    aux suspect 
      | currentIsPrime = suspect : nextPrimes
      | otherwise      = nextPrimes
      where
          currentIsPrime =
            all (\n -> suspect `mod` n /= 0)
            $ takeWhile (\n -> n*n <= suspect) allPrimes
          nextPrimes = aux (suspect + 2) 

nthPrime :: Int -> Integer
nthPrime n = allPrimes !! (n-1)