haskell - Totient-function generating sieve consuming too much memory -

i have written sieve-based generator list of totients, , want take sum 1000000.

applyevery :: (a -> a) -> int -> [a] -> [a] applyevery f n xs = xf ++ (\(y:ys) -> f y : applyevery f n ys) xb       (xf, xb) = splitat (n - 1) xs  totients :: [int] totients = 1 : sieve [2..] [2..]        sieve (x:xs) (y:ys)          | x == y    = (y - 1) : sieve xs (propagateprime x ys)           | otherwise = y : sieve xs ys     propagateprime j = applyevery (\x -> (quot x j)*(j - 1)) j  totientsum :: int -> int totientsum n = sum $ take n totients 

when computing totientsum n n above 40000, ghci takes ages evaluate , starts consuming tremendous amounts of memory. compiling executable doesn't help. assume has way haskell handles lazy evaluation.

i know if it's possible selectively apply strictness improve memory consumption of above functions can compute totient sum 1000000. know if there's better way using lists, or if should use random-access data structure. if know of faster algorithm computing totient sum, please share reference.

i thought definition of applyevery might make difference, tried following other implementations, both seemed consume more memory definition used above.

-- <https://www.reddit.com/2tpqip/> applyevery' :: (a -> a) -> int -> [a] -> [a] applyevery' f n = zipwith ($) (cycle (replicate (n - 1) id ++ [f]))  applyevery'' :: (a -> a) -> int -> [a] -> [a] applyevery'' f n xs = xf ++ (\(y:ys) -> f y : applyevery'' f n ys) xb       xf = take (n - 1) xs     xb = drop (n - 1) xs 

in implementing euler product formula:

you can take advantage of fact calculating euler phi numbers numbers in range [1..n]

doing so, may first find primes in range [1..n] , instead of finding prime divisors of each number, find multiples of each prime number. obviously, latter can done more efficiently.

a possible implementation be:

import data.int (int64) import control.applicative ((<$>)) import data.array.unboxed (uarray, elems, accum, listarray)  primes :: integral => [a] primes = 2: 3: filter pred (chain [5,11..] [7,13..])         chain (x:xs) (y:ys) = x: y: chain xs ys     pred = (\i -> `mod` /= 0) $ takewhile (\i -> * <= a) primes  euler_phi :: int64 -> [int64] euler_phi n = elems $ accum (\a p -> - `div` p) arr inc         val = takewhile (<= n) primes     idx = map (\i -> takewhile (<= n) [i,2 * i..]) val      inc = concat $ zipwith (\i j -> ($j) <$> (,) <$> i) idx val     arr = listarray (1, n) [1..n] :: uarray int64 int64  main = getline >>= print . sum . euler_phi . read 

then:

\> euler_phi 20 [1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8] 

would euler totient function first 20 numbers; , if compile -o2 flag may calculate cumulative sums pretty decent performance:

$ ghc --make -o2 euler_phi.hs [1 of 1] compiling main             ( euler_phi.hs, euler_phi.o ) linking euler_phi ...  $ time echo 40000 | ./euler_phi 486345716  real    0m0.091s user    0m0.040s sys     0m0.006s