<br><div><span class="gmail_quote">On 8/29/07, <b class="gmail_sendername">David Frey</b> <<a href="mailto:dpfrey@shaw.ca">dpfrey@shaw.ca</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hello Haskellers,<br><br>I have been trying to learn a bit about Haskell by solving Project Euler<br>problems. For those of you who don't know what Project Euler is, see<br><a href="http://projecteuler.net">http://projecteuler.net
</a><br><br>After solving problem 21, which is related to amicable pairs, I decided<br>to attempt problem 95 since it is an extension of the same topic.<br><br>The full description of problem 95 is here:<br><a href="http://projecteuler.net/index.php?section=problems&id=95">
http://projecteuler.net/index.php?section=problems&id=95</a><br><br>This is the summary:<br>"Find the smallest member of the longest amicable chain with no element<br>exceeding one million."<br><br>I have attempted to solve this problem, but my solution is too resource
<br>hungry to search the full set of 1000000 numbers.<br><br>I am hoping someone reading this list can suggest :<br> - How I can improve my algorithm<br> - An alternative algorithm that will be more efficient<br> - Ways to profile a Haskell program to help me understand why my
<br> implementation is performing poorly.<br><br>In addition to the question above, I would also be interested in<br>comments on the style of the code. If there is a more idiomatic way to<br>write portions of the code, I would like to see what it is.
<br><br>My solution is at the bottom of this e-mail. The program will probably<br>run obscenely slow or die from stack overflow unless you replace<br>[1..999999] with [1..somethingSmaller] in main.<br><br>Thanks,<br>David Frey
</blockquote><div><br>Hi David,<br><br>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!).
<br><br>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). 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
<a href="http://haskell.org/haskellwiki/Stack_overflow">http://haskell.org/haskellwiki/Stack_overflow</a>.<br><br>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. 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
<a href="http://haskell.org/haskellwiki/Performance">http://haskell.org/haskellwiki/Performance</a> to see if it gives you any ideas.<br><br>Hope this helps,<br>-Brent<br></div></div>