Well, after some thought, I decided to try re-writing the boolean primes
map program only using a list instead of an array. I came up with this
program:


primes :: Int -> [Int]
primes how_much =  (iterate 2 initial_map) where
        initial_map :: [Bool]
        initial_map = (map (\x -> True) [ 0 .. how_much])
        iterate :: Int -> [Bool] -> [Int]
        iterate p (a:as) | p > mybound = process_map p (a:as)
                         | a = p:(iterate (p+1) (mymark (p+1) step (2*p) as))
                         | (not a) = (iterate (p+1) as) where
                                step :: Int
                                step = if p == 2 then p else 2*p
        mymark :: Int -> Int -> Int -> [Bool] -> [Bool]
        mymark cur_pos step next_pos [] = []
        mymark cur_pos step next_pos (a:as) = 
                if (cur_pos == next_pos) then
                        False:(mymark (cur_pos+1) step (cur_pos+step) as)
                else
                        a:(mymark (cur_pos+1) step next_pos as)
        mybound :: Int
        mybound = ceiling(sqrt(fromIntegral(how_much)))
        process_map :: Int -> [Bool] -> [Int]
        process_map cur_pos [] = []
        process_map cur_pos (a:as) | a = cur_pos:(process_map (cur_pos+1) as)
                                   | (not a) = (process_map (cur_pos+1) as)
                                        
I don't know too much about Haskell yet, so it is possible this program
can be further optimized using some Haskell built-ins.

Now, this program can scale to 100,000 and beyond, as opposed to the array
version which only got until 30,000 or 40,000. It's a pity Haskell doesn't
handle arrays very well, but I guess every language has its faults.

Regards,

        Shlomi Fish


----------------------------------------------------------------------
Shlomi Fish        [EMAIL PROTECTED] 
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [EMAIL PROTECTED]

The prefix "God Said" has the extraordinary logical property of 
converting any statement that follows it into a true one.


_______________________________________________
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to