[Haskell-cafe] Re: tail recursion ?

Simon Brenner simbr843 at student.liu.se
Mon Jun 11 15:37:35 EDT 2007


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).


More information about the Haskell-Cafe mailing list