[Haskell-cafe] Memory allocation in extractor function (newbie question)

[Yitzchak Gale]

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