[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
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]]
--
--
Thanks for you answers in advance
H.
More information about the Haskell-Cafe
mailing list