[Haskell-cafe] tail recursion ?

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 

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 

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
  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]]

Thanks for you answers in advance

More information about the Haskell-Cafe mailing list