Consider foldl (+) 0 [x1,x2,x3,x4,... This rewrites to foldl (+) (0 + x1) [x2,x3,x4,...] ==> foldl (+) (0 + x1 + x2) [x3,x4,...] ==> foldl (+) (0 + x1 + x2 +x3) [x4,...] And so on. So we build up a giant chain of thunks. Finally we evaluate the giant chain, and that builds up a giant stack. Why can't GHC evaluate as it goes? Because it's only correct to do so if the function is strict in its second argument, which (+) is, and so is addToFM. If GHC were to inline foldl more vigorously, this would happen. Maybe we should make it do so, to avoid gratuitous leaks. Simon | -----Original Message----- | From: Julian Assange [mailto:proff@iq.org] | Sent: 24 February 2001 10:50 | To: haskell@haskell.org | Cc: proff@iq.org | Subject: stack overflow | | | -- compile with: | -- ghc -i/usr/lib/ghc-4.08.1/imports/data -lHSdata | -fglasgow-exts -O -fglasgow-exts wordfreq.hs -o wordfreq | module Main where | import List | import Char(toLower) | import FiniteMap(fmToList,emptyFM,addToFM,lookupWithDefaultFM) | | main = interact (unlines . pretty . sort . fmToList . | makemap . words . lower) | where | pretty l = [w ++ " " ++ show n | (w,n) <- l] | sort = sortBy (\(_,n0) (_,n1) -> compare n0 n1) | makemap = foldl f emptyFM | where | f fm word = addToFM fm word (n+1) | where | n = lookupWithDefaultFM fm 0 word | lower = map toLower | | | | When used with a 170k input file, makemap suffers from a stack | overflow. foldl should be tail recursive. What's the score? | | Julian | | _______________________________________________ | Haskell mailing list | Haskell@haskell.org | http://www.haskell.org/mailman/listinfo/haskell |