[Haskell-cafe] Re: Strange space leak

[apfelmus]

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