Journey into Haskell, part 6

Another thing to be learned down the Haskell rabbit-hole: Thinking in infinites. Today someone posed a puzzle which I tried to solve in a straight-forward, recursive manner: Building a list of primes. The requested algorithm was plain enough:

Create a list of primes “as you go”, considering a number prime if it can’t be divided by any number already considered prime.

However, although my straightforward solution worked on discrete ranges, it couldn’t yield a single prime when called on an infinite range — something I’m completely unused to from other languages, except for some experience with the SERIES library in Common Lisp.

An incomplete solution

Looking similar to something I might have written in Lisp, I came up with this answer:

primes = reverse . foldl fn []
    where fn acc n
              | n `dividesBy` acc = acc
              | otherwise         = (n:acc)
          dividesBy x (y:ys)
              | y == 1         = False
              | x `mod` y == 0 = True
              | otherwise      = dividesBy x ys
          dividesBy x [] = False

But when I suggested this on #haskell, someone pointed out that you can’t reverse an infinite list. That’s when a light-bulb turned on: I hadn’t learned to think in infinites yet. Although my function worked fine for discrete ranges, like [1..100], it crashed on [1..].

So back to the drawing board, later to come up with this infinite-friendly version:

primes :: [Int] -> [Int]
primes = fn []
    where fn _ [] = []
          fn acc (y:ys)
              | y `dividesBy` acc = fn acc ys
              | otherwise         = y : fn (y:acc) ys

          dividesBy _ [] = False
          dividesBy x (y:ys)
              | y == 1         = False
              | x `mod` y == 0 = True
              | otherwise      = dividesBy x ys

Here the accumulator grows for each prime found, but returns results in order whose value can be calculated as needed. This time when I put primes [1..] into GHCi it printed out prime numbers immediately, but visibly slowed as the accumulator grew larger.