Alexander Kireyev wrote:
While trying to write a program for the countPaths Code Jam problem I ran into what seems to me as a weird behaviour in terms of memory allocation... The profiling log (./paths +RTS -P) shows the following time/space behaviour for them...
Hi Alexander, I'm not sure I can fully explain your profiling behavior either, but I'll take a stab at what the problem might be anyway. You didn't show us the code for countForPoints. I'll bet you wrote something like countForPoints area ls count points = sum $ map (countPathsFrom area (count + 1) ls) points Unfortunately, the standard sum function is too lazy in many situations. And if you wrote out the recursion for countForPoints by hand, you may have run into the same problem. In either case, you'll be accumulating huge amounts of unevaluated (+) thunks instead of adding up the count as you go along. If this is the problem, you can fix it by using foldl', a strict version of foldl from Data.List, instead of sum: countForPoints area ls count points = foldl' (+) 0 $ map (countPathsFrom area (count + 1) ls) points Hope this helps, Yitz