[Haskell-cafe] Re: tail recursion ?

12 Jun 2007

      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.