Am Mittwoch 13 Januar 2010 20:58:17 schrieb Tim Perry:
A side benefit of using foldl' instead of foldr is that I can now run it against the entire dictionary!
I found a good explanation of why here: http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27
Yep. One thing, though: seq, and hence foldl' only evaluates to weak head normal form (WHNF), that is (leaving aside lambda expressions), to the topmost constructor. So, e.g. list `seq` value only checks whether list is [] or (_:_), that may not be enough strictness in a fold. The constructors of Map are strict enough to avoid large thunks in general with foldl', but for example to compute the average of a list of numbers: average :: [Double] -> Double average list = sumList / countList where (sumList,countList) = foldl' add (0,0) list add (s,c) x = (s+x,c+1) isn't strict enough, sumList and countList will be large thunks because in each step add (s,c) x will be evaluated enough only to see that it is indeed a pair. For such cases, one needs to force the evaluation further by hand. One possibility is to write a stricter function: add' (s,c) x = let s1 = s+x c1 = c+1 in s1 `seq` c1 `seq` (s1,c1) or, using BangPatterns: add' (!s,!c) x = (s+x,c+1) Another possibility is to use a sufficiently strict data type data DPair = DP !Double !Double add (DP s c) x = DP (s+x) (c+1) (the strict fields will keep the numbers completely evaluated at each step), a third is to use rnf {- reduce to normal form -} from Control.Parallel.Strategies or another sufficiently strict strategy, respectively deepseq. Which one is the best choice varies of course.