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

Alexander Kireyev alexander.kireyev+haskell.cafe at gmail.com
Mon Apr 7 10:10:30 EDT 2008

On Mon, Apr 7, 2008 at 4:16 PM, Yitzchak Gale <gale at sefer.org> wrote:
>  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

Thanks for the pointer. In fact my version was already using the fold
function, albeit the lazy version of it:

countForPoints :: Area -> String -> Int -> [Point] -> Int
countForPoints area goal count points =
   let newCount = foldl (countSubPaths area goal) count points
   in if countExceeded newCount
      then -1
      else newCount

countExceeded :: Int -> Bool
countExceeded count = (count < 0) || (count > countLimit)

countSubPaths :: Area -> String -> Int -> Point -> Int
countSubPaths area goal count point =
 if (countExceeded count)
 then -1
 else countPathsFrom area count goal point

Switching to the strict version reduced the amount of garbage in that
function and in countSubPaths, but the problem with 'letterAt' still
shines. I was thinking that adding strictness to that function might
help, but no amount of exclamation marks helped it so far.

// copying to the mailing list, because first reply didn't get through.

More information about the Haskell-Cafe mailing list