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
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.