[Haskell-cafe] In-place modification

[Chaddaï Fouché]

2007/7/15, Hugh Perkins <hughperkins at gmail.com>:
> There's really a tendency in this newsgroup to point people to huge
> documents, when a small copy and paste would make the answer so much more
> accessible ;-)

I was pointing you on a document of quite honest size in my opinion,
and not really hard to read...
But well if you want a piece of code, here it is :
--

merge xs@(x:xt) ys@(y:yt) = case compare x y of
    LT -> x : (merge xt ys)
    EQ -> x : (merge xt yt)
    GT -> y : (merge xs yt)

diff  xs@(x:xt) ys@(y:yt) = case compare x y of
    LT -> x : (diff xt ys)
    EQ -> diff xt yt
    GT -> diff xs yt

primes, nonprimes :: [Int]
primes    = [2,3,5] ++ (diff [7,9..] nonprimes)
nonprimes = foldr1 f . map g $ tail primes
    where f (x:xt) ys = x : (merge xt ys)
          g p = [ n*p | n <- [p,p+2..]]

-- 
The HaskellWiki repertory it under "primes" and it's at least 170
times faster than the extra-naive sieve you used in your comparison on
my computer... (I have some doubts on the accuracy of the benchmark
and System.Time at this level of precision, especially on Windows)

An implementation with DiffArray (not even DiffUArray since there's no
instance for Bool ? Is there a bitvector implementation somewhere to
make up for this ?) and exactly your algorithm is already more than 20
times faster than the naive sieve.

Note that this kind of benchmark is pretty pointless anyway since
you're not really using C# in your program : you're using a subset of
C# that's almost immediately translatable in the corresponding C code,
and indeed the JIT compiler must compile to the same code as the
equivalent C code, so it's no surprise at all that the performances
are similar !
Due to the nature of Haskell, it's not so easy to do the same thing
(write a C program in Haskell as you wrote a C program in C#), so the
conclusion is obviously to Haskell disadvantage.

-- 
Jedaï