[Haskell-cafe] newbie optimization question

Tillmann Rendel rendel at rbg.informatik.tu-darmstadt.de
Sun Oct 28 15:41:19 EDT 2007


Prabhakar Ragde wrote:
> divisors i = [j | j<-[1..i-1], i `mod` j == 0]
> main = print [i | i<-[1..10000], i == sum (divisors i)]

Jerzy Karczmarczuk wrote:
> My point didn't concern that point. Haskell compiler cannot change an
> algorithm using lists into something which deals with indexable arrays,
> usually faster. Indexing may be faster than the indirection, and the
> allocation of memory costs. And there is laziness...

This may be true, but it isn't relevant in this case, since the "obvious 
c program" doesn't need any arrays, only two loops:

for (int i = 1; i <= 10000; i++) {
   int sum = 0;
   for (int j = 1; j < i; j++)
     if (i % j == 0)
       sum += i;
   if (sum == i)

Loops can be expressed with lazy lists in Haskell. Therefore, the 
presented Haskell program is perfectly equivalent to the "obvious c 

   Tillmann Rendel

More information about the Haskell-Cafe mailing list