[Haskell-beginners] Is foldr slow?

2 Feb 2012

      Hi,

When I refactor my Segmented Seive of Eratosthenes, I'm puzzled by the performance of "foldr".
Here is my original code. I realized that "sieveWith"(Integral a => ([a], [a]) -> ([a], [a]), it takes a tuple with sieving primes and prime candidates, and remove all multiplies of sieving primes in candidates, at last return a tuple with blank sieving primes and a pure primes list) in "primesFromTo" is not much readable and can be replaced by "foldr".

But when I did, I find it would take about 5 seconds to sieve primes between 999900000 and 1000000000, whereas the original one just takes 1.6 
seconds. The "sieveWith" function is the only place I change. I also have tried foldr', which does not much help. Is foldr slow? Or did I make any 
mistake? Thanks.

=== Origin (./main < data1.txt  1.45s user 0.11s system 99% cpu 1.562 total) ===
{-# OPTIONS_GHC -O2 #-}

import Data.List
import System.IO

minus (x:xs) (y:ys) = case (compare x y) of 
           LT -> x : minus  xs  (y:ys)
           EQ ->     minus  xs     ys 
           GT ->     minus (x:xs)  ys
minus  xs     _     = xs

intSqrt :: Integral a => a -> a
intSqrt = floor . sqrt . fromIntegral

primesTo :: Integral a => a -> [a]
primesTo x = 2 : sieve [3, 5 .. x] where
    sieve ns@(n : rs)
        | n <= intSqrt x    = n : sieve (rs `minus` [n * n, n * (n + 2) .. x])
        | otherwise         = ns
    sieve [] = []

candidatesBetween :: Integral a => a -> a -> [a]
candidatesBetween x y = let x' = if odd x then x else x + 1 in [x', x' + 2 .. y]

primesFromTo :: Integral a => a -> a -> [a]
primesFromTo x y
    | x < 2 = primesTo y
    | otherwise = snd . sieveWith $ (primes, candidates) where
        primes = tail . primesTo . intSqrt $ y
        candidates = candidatesBetween x y
        sieveWith (a : as, bs'@(b : bs)) = sieveWith (as, bs' `minus` multiplies a b) where
        sieveWith ([], bs) = ([], bs)
        multiplies a b = let b' = b + ((-b) `mod` a) in [b', b' + 2 * a .. y]

primesFromTo' [x, y] = primesFromTo x y

main :: IO ()
main = do
    count <- fmap read getLine
    inputLines <- fmap (take count . lines) getContents
    let answers = map (primesFromTo' . map read . words) inputLines
    putStr . unlines . map (unlines . map show) $ answers

=== Origin ===

=== New (./main < data1.txt  4.76s user 0.15s system 99% cpu 4.917 total) ===
{-# OPTIONS_GHC -O2 #-}

import Data.List
import System.IO

minus (x:xs) (y:ys) = case (compare x y) of 
           LT -> x : minus  xs  (y:ys)
           EQ ->     minus  xs     ys 
           GT ->     minus (x:xs)  ys
minus  xs     _     = xs

intSqrt :: Integral a => a -> a
intSqrt = floor . sqrt . fromIntegral

primesTo :: Integral a => a -> [a]
primesTo x = 2 : sieve [3, 5 .. x] where
    sieve ns@(n : rs)
        | n <= intSqrt x    = n : sieve (rs `minus` [n * n, n * (n + 2) .. x])
        | otherwise         = ns
    sieve [] = []

candidatesBetween :: Integral a => a -> a -> [a]
candidatesBetween x y = let x' = if odd x then x else x + 1 in [x', x' + 2 .. y]

primesFromTo :: Integral a => a -> a -> [a]
primesFromTo x y
    | x < 2 = primesTo y
    | otherwise = sieveWith primes candidates where
        primes = tail . primesTo . intSqrt $ y
        candidates = candidatesBetween x y
        -- sieve a list of candidates with sieving primes
        -- foldr version: ./main < data1.txt  4.76s user 0.15s system 99% cpu 4.917 total
        sieveWith ps'@(p : ps) cs'@(c : cs) = foldr (\a b -> b `minus` (multiplies a c)) cs' ps'
        sieveWith [] cs = cs
        multiplies a b = let b' = b + ((-b) `mod` a) in [b', b' + 2 * a .. y]

primesFromTo' [x, y] = primesFromTo x y

main :: IO ()
main = do
    count <- fmap read getLine
    inputLines <- fmap (take count . lines) getContents
    let answers = map (primesFromTo' . map read . words) inputLines
    putStr . unlines . map (unlines . map show) $ answers

=== New ===

Best regards,
Zhi-Qiang Lei
zhiqiang.lei@gmail.com