eratosthenes.hs

-- my implementation of this: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

import qualified Data.PSQueue as DQ

insertThenDel k p pq = DQ.deleteMin $ DQ.insert k p pq

minPriority pq = 
            case DQ.findMin pq of
                (Just m) -> 
                    let mp = DQ.prio m
                        mk = DQ.key m
                        in Just (mp, mk)
                Nothing -> Nothing

removeComposites smallest pq =
    let Just (mp, mk) = minPriority pq 
        in case smallest < mp of
            True -> pq
            _    -> 
                let nextk = tail mk
                    nextp = mk !! 1 
                    pq' = insertThenDel nextk nextp pq
                    in removeComposites smallest pq'

-- "base case" of corecursion if a finite list is passed in

insertPrime p xs pq = DQ.insert (map (*p) xs) (p*p) pq

sieve' [] pq = []
sieve' (x:xs) pq = 
    case minPriority pq of
        Just (mp, mk) -> 
            case x == mp of
                True -> sieve' xs (removeComposites x pq)
                False -> x : (sieve' xs $ insertPrime x (x:xs) pq)
        Nothing -> x : (sieve' xs $ insertPrime x (x:xs) pq)

sieve xs = 2:(sieve' xs DQ.empty)

main = do
        print $ sum $ takeWhile (<2000000) $ sieve [3,5..]