[Haskell-cafe] newbie optimization question

[Derek Elkins]

On Sun, 2007-10-28 at 10:23 -0400, Prabhakar Ragde wrote:
> Jaak Randmets wrote:
> > On 10/28/07, Prabhakar Ragde <plragde at uwaterloo.ca> wrote:
> >> For the purposes of learning, I am trying to optimize some variation of
> >> the following code for computing all perfect numbers less than 10000.
> >>
> >> divisors i = [j | j<-[1..i-1], i `mod` j == 0]
> >> main = print [i | i<-[1..10000], i == sum (divisors i)]
> >>
> >> I know this is mathematically stupid, but the point is to do a moderate
> >> nested-loops computation. On my 2.33GHz dual-core MacBookPro, the
> >> obvious C program takes about .3 seconds, and a compiled OCaML program
> >> (tail recursion, no lists) about .33 seconds. The above takes about 4
> >> seconds.
> >>
> > 
> > You could try giving divisors type signature:
> > divisors :: Int -> [Int]
> 
> Thank you. That brings the time down to 0.5 seconds. I'm glad it was 
> something as simple as that. --PR

I'm not sure if Jaak Randmets explained this, but the reason this makes
a difference is that Haskell defaults to Integer, an arbitrary precision
integer type, that is far more costly than an Int.