[Haskell-cafe] Looking for suggestions to improve my algorithm

[Daniel Fischer]

Am Donnerstag, 30. August 2007 01:08 schrieb Brent Yorgey:
> Hi David,
>
> Project Euler is a good way to learn some Haskell, although it does tend to
> give you a crash course in understanding laziness, efficiency and such in
> Haskell (whether that's good or bad depends on your point of view!).
>
> All you need to do to stop your program from overflowing the stack is to
> change foldl to foldl' in the definition of main (foldl' is in Data.List so
> you'll also have to import that). 

I didn't even need to do that. Worked fine for me as it is (I compiled with 
-O2, that probably helped).

> The problem with foldl is that since
> Haskell is lazy, instead of evaluating things as it goes along, it builds
> up a huge string of thunks (=unevaluated expressions) and doesn't even
> start evaluating anything until it reaches the end of the list, which can
> easily blow the stack.  foldl' is a strict version of foldl which forces
> evaluation to take place as it goes along.  For an excellent explanation of
> all of this, I suggest you read
> http://haskell.org/haskellwiki/Stack_overflow.
>
> As soon as I replaced foldl with foldl' in your code, it no longer
> overflows the stack -- however, it's still quite slow!  I didn't wait long
> enough for it to finish when I ran it up to a million.

45 seconds on my 1200MHz thing, not incredibly fast, but not obscenely slow 
either.

>  I don't have any
> advice on that front at the moment, perhaps someone else will come along
> with a suggestion or two.  In the meantime, you can poke around
> http://haskell.org/haskellwiki/Performance to see if it gives you any
> ideas.
>
> Hope this helps,
> -Brent

Cheers,
Daniel