This blog has been rather neglected, but I’m getting towards the end of my batch at the Recurse Center in New York so I’m going to try updating it again.

My previous post showed a code-golfed prime sieve I wrote for fun in Haskell.

-- generate a list of prime numbers less than or equal to n
import Data.List
primeList :: Integral a => a -> [a]
primeList n = nubBy (\x y-> x`mod`y==0) [2..n]

While trying to solve problem 35 from Project Euler (“How many circular primes are there under 1,000,000”), I found myself needing something like this again. Unfortunately, nubBy has quite bad performance in this situation, so the one-line version is really inefficient. But, using Data.Vector there turns out to be a much faster option:

import qualified Data.Vector as V (Vector(..),fromList,toList, (//), (!), foldl')

candidates :: Int -> V.Vector Int
candidates n = (V.fromList [2..n]) V.// filters
  where filters = concat $ map (\x -> isMult x n) [2..n]

isMult :: Int -> Int -> [(Int,Int)]
isMult x u = [(x*m-2,0) | m <- [2..(u `div` x)]]

This version takes the vector of numbers [2..1000000] and sets all element that are multiples of any other number in the vector to 0, taking advantage of the fact that Vector has $O(1)$ indexing, rather than $O(n)$ for lists, and Data.Vector’s batch update operator // so updates can be staged and done all at once rather than done individually. This is not surprisingly much faster than recursively filtering a list as is done with nubBy. There’s still some redundancy in how isMult generates updates, plus some less-than-ideal fiddling with indexes, so there’s a lot of space for improvement, but using this instead of the list-based version took the full solution from unusably slow to running in ~7 seconds.