Grzegorz Chrupala wrote:
Hi all,
I just noticed that a tiny change to the program which I posted recently in
the "More idiomatic use of strictness" thread causes a space leak.
The code is:
{-# LANGUAGE BangPatterns, PatternGuards #-}
import Data.List (foldl')
import Data.Char
split delim s
| [] <- rest = [token]
| otherwise = token : split delim (tail rest)
where (token,rest) = span (/=delim) s
main = do
putStrLn =<< fmap (show . stats ["the","a","and"] . split "<DOC>" . words)
getContents
stats ws docs = foldl' f ((map (const 0) ws),0) docs
where f (dfs,n) d = let dfs' = zipWith (\w df -> (df + fromEnum (w
`elem` d))) ws dfs
in sum dfs' `seq` (dfs',n+1)
If I change this line:
putStrLn =<< fmap (show . stats ["the","a","and"] . split "<DOC>" . words)
getContents
to this:
putStrLn =<< fmap (show . stats ["the","a","and"] . split "<DOC>" . words
.. map toLower) getContents
suddenly the programs starts using tons of memory instead of running in
small constant space.
What's going on?
Answer:
split "<DOC>" . words . map toLower = (:[]) . words . map toLower
Since you converted everything to lowercase, the string "<DOC>" will
never appear in the text, resulting in a single huge document.
Furthermore, due to `elem` d , your stats function takes space
proportional to the length of each document it processes.
Beauty & makeup tips:
putStrLn =<< fmap f getContents
= putStrLn . f =<< getContents
~= interact f
Here's a version with glittering nail polish that should run in constant
space:
split y xs = zs : case xs' of
[] -> []
_:xs' -> split y xs'
where (zs,xs') = break (==y) xs
main = interact $
show . stats ["the","a","and"] . split "<DOC>" . words
zipWith' f xs ys = zipWith f xs ys `using` rnf
stats ws = foldl' (zipWith' (+)) zero
. map (foldl' (zipWith' max) zero . map bits)
where
zero = map (const 0) ws
bits v = map (fromEnum . (== v)) ws
Regards,
apfelmus
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
