[Haskell-cafe] Why does this program eat RAM?

[Udo Stenzel]

John Goerzen wrote:
> I have the below program, and I'm trying to run it on an input of about
> 90MB.  It eats RAM like crazy, and I can't figure out why.
> 
> wordfreq inp = Map.toList $ foldl' updatemap (Map.empty::Map.Map String Int) inp
>     where updatemap nm word = Map.insertWith updatefunc word 1 nm
>           updatefunc _ x = x + 1

The culprit is insertWith, it inserts unevaluated thunks into your map
where you want a simple value.  To avoid a space leak, you want a strict
update function (yours is strict enough) and insertWith must be strict
in the newly inserted value (the result of applying updatefunc).  Since
you cannot influence the strictness of insertWith, no matter how many
seqs you sprinkle through your code, you need insertWith', which is
missing.  You can simulate it, however:

insertWith' f k v m = case Map.lookup k m of
	Nothing -> Map.insert k v m
	Just w  -> (Map.insert k $! f w v) m

IMHO all accumulating functions, especially foldl, State.update,
Map.insertWith, accumArray, absolutely need a strict version, because
the strictness cannot be recovered by the library's user.  If the
clutter of too many primed names is unbearable, leave out the _lazy_
version.  It's useless IME and lazyness can be recovered if the need
arises.


Udo.
-- 
Wo die Macht geistlos ist, ist der Geist machtlos.
	-- aus einem Gipfelbuch
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060905/3251b271/attachment.bin