[Haskell-beginners] Is foldr slow?

[Chaddaï Fouché]

On Thu, Feb 2, 2012 at 5:16 PM, Zhi-Qiang Lei <zhiqiang.lei at gmail.com> wrote:
> 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".
>

let go a b = b `minus` (multiplies a c)
foldr go cs' (p:p':ps) ==> foldr go cs' (p':ps) `minus` multiplies p c
==> (minus needs his first argument to start removing stuff) (foldr go
cs' ps `minus` multiplies p' c) `minus` multiplies p c
And so on and so forth...
In other words, contrary to your first version, this function must
develop the entire list before making its first suppression...

Your version rather correspond to a foldl (be careful of strictness,
using foldl it's pretty easy to get big thunks).

Foldr is very useful for functions that are lazy in their second
argument like (||) , (&&),  (:) or others but if the function is
strict in its second argument like yours (strict in b)...

-- 
Jedaï