Jon Fairbairn writes:

The idea in Haskell is not to think of stepping through the array. Look at accumArray and ixmap.

Thanks for your answer. But I can't really see how the calc-function can be written more efficiently with accumArray or ixmap, perhaps you can write it as an example? -- Regards, H.

The key is letting haskell be lazy and produce the output one item at a time. My solution below generates a list of all indices to be inversed (with indices being duplicated as appropriate), then for each index in that list inverses the corresponding element in the array. The list can be written compactly using either list comprehensions or list monads. Using list monads:

listOfIndices ubound = [1..ubound] >>= \i -> [i,(2*i) .. ubound]

and using list comprehension and concatenation - slightly longer but probably more readable:

listOfIndices' ubound = concat [ [i,(2*i) .. ubound] | i <- [1..ubound] ]

const . not == (\x _ -> (not x)), i.e. a function that discards the second argument and returns the complement of the first.

calc ubound = accumArray (const.not) False (1,ubound) $ [(x,False) | x <- listOfIndices ubound]

zip [1..] (elems arr) == assocs arr putStrLn . unlines . map show ~~ mapM_ print

main = mapM_ print $ filter snd $ assocs $ calc 100000

This solution goes up to 100k in 25M of heap and up to 400k in 200M of heap. While working better, the space requirement seems to be (at least almost) quadratic, so this is probably not a complete solution to your problem (unless all you really needed was those 10k elements, or at most 400k).

Simon Brenner writes:

...

listOfIndices' ubound = concat [ [i,(2*i) .. ubound] | i <- [1..ubound] ] calc ubound = accumArray (const.not) False (1,ubound) $ [(x,False) | x <- listOfIndices ubound]

Thanks a lot! Your solution works fine as long as there are not to much modifications (you mentioned the memory...) -- accumArray ----------------------------------- 20 Mb total memory in use INIT time 0.02s ( 0.00s elapsed) MUT time 1.73s ( 1.81s elapsed) GC time 2.83s ( 2.86s elapsed) EXIT time 0.00s ( 0.01s elapsed) Total time 4.59s ( 4.68s elapsed) So I tried another possibility, STUArrays, which are significantly faster and use less memory: ------------------------------------------------- main = mapM_ print $ filter snd $ runST calc x = 100000 :: Int calc = do arr <- newArray (1,x) False :: ST s (STUArray s Int Bool) calc' arr d <- getAssocs arr return (d) where calc' arr = f 1 where f a | a < x = g a >> f (a+1) | otherwise = g a where g b | b <= x = readArray arr b >>= \i-> writeArray arr b (not i) >> g (b+a) | otherwise = return () ------------------------------------------------- (it is the first time I'm using this Type) -- STUArray ------------------------------------- 8 Mb total memory in use INIT time 0.01s ( 0.00s elapsed) MUT time 0.21s ( 0.28s elapsed) GC time 0.21s ( 0.21s elapsed) EXIT time 0.00s ( 0.01s elapsed) Total time 0.43s ( 0.49s elapsed) But 8MB seems still too much, how can it be further optimised? -- Best Regards and thanks for you answers in advance H.