[Haskell-cafe] Re: Haskell version of Norvig's Python Spelling Corrector

[Udo Stenzel]

Pete Kazmier wrote:
>   train:: [B.ByteString] -> WordFreq
>   train words = frequencyMap
>       where
>         frequencyMap     = foldr incWordCount M.empty words
>         incWordCount w m = M.insertWith (+) w 1 m
> 
> So is 'incWordCount' strict in its second argument?  I'm still not
> sure exactly what that means.

Yes.  incWordCount is strict in its second argument since

incWordCount x undefined == undefined

Of course you cannot see that from the definition of incWordCount alone,
this depends on the behavior of M.insertWith.  

> According to the wiki page, if it is
> strict in the second argument, I should have used foldl' instead of
> foldr.

Remember that the difference between foldr and foldl is not one between
left and right; both have to recurse from the left.  But foldr is normal
recursion, while foldl is accumulator recursion.  You obviously wanted
an accumulator, and it should usually be strictly evaluated.

There is another bug of this sort in your code.  Consider

>         incWordCount w m = M.insertWith (+) w 1 m

There is no reason to evaluate the sum inside the map, instead an
unevaluated thunk is put in there.  Unfortunately, you need to take the
long way of using M.lookup and M.insert to build a strict replacement
for M.insertWith.  (A strict variant of Data.Map would be useful here,
unfortunately, there is none.)


-Udo
-- 
Streitigkeiten dauerten nie lange, wenn nur eine Seite Unrecht hätte.
	-- de la Rochefoucauld
-------------- 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/20070424/1f56e8ce/attachment.bin