H. h._h._h._ at hotmail.com
Mon Jun 11 09:44:36 EDT 2007

```Hello @ all,

Sometimes one has an imperative algorithm, and wants to write a program in
Haskell which do has the same effect...

So the question is - how a construct as the following can efficiently be
written?

--
Pseudo code:
n[1..10000] = false
for (1..10000) |i|
for (i,2*i..10000) |j|
n[j] = not n[j]
--

Certainly it is in this special case equivalent to (True where the index is):
map (^2) [1..100]

But I mean the destructive updates in the imperative code in Haskell without
filling the (many times more than in imperative languages) memory with
recursively called functions...

The idea, I thought, is tail recursion, so perhaps I just have a big bug in my
code, caused by the fact, that it needs even for 5000 approximately 100MB
memory:

--
import Data.Array

main :: IO ()
main = putStr \$! unlines \$! map show \$! filter snd
\$! zip [1..] \$! elems \$! calc \$! la 5000
where la x = array (1,x) [(y,False)|y<-[1..x]]

calc :: Array Int Bool -> Array Int Bool
calc x = f 1 x
where
k :: Int
k = snd \$ bounds x
f :: Int -> Array Int Bool -> Array Int Bool
f !a !x | a < k     = f (a+1) \$! g a x
| otherwise = g a x
g !a !x = x//[(j,not (x!j))|j<-[a,a*2..k]]
--

--