<div dir="ltr"><br><div class="gmail_quote">---------- Forwarded message ----------<br>From: <b class="gmail_sendername">John Lusk</b> <span dir="ltr"><<a href="mailto:johnlusk4@gmail.com">johnlusk4@gmail.com</a>></span><br>Date: Sat, Oct 24, 2015 at 3:25 PM<br>Subject: Space consumption and strictness in strict map<br>To: <a href="mailto:beginners@haskell.org">beginners@haskell.org</a><br><br><br><div dir="ltr">Hey, I have a problem I "solved" by sprinkling !s around like pixie dust, but I'd like to know what's going on.  I'll attach my program, in all its messy glory, but the whole ball of wax is at <a href="https://github.com/JohnL4/PassphraseGenerator" target="_blank">https://github.com/JohnL4/PassphraseGenerator</a>.  It takes as input one of the 2012 Google ngram (specifically, 1-gram) raw data files.  The expected input format is documented in several places.  (For testing, I took the first million lines.)<div><br></div><div>The bang that worked is on the 3rd argument of '<font face="monospace, monospace">wordCount</font>', the map.  I tried commenting out the "<font face="monospace, monospace">(Map.insertWith (+) ngram matchCount aMap)</font>" part (and just returning the input map).  When I did that, boy was space consumption small, so that line is part of the problem.</div><div><br></div><div>So, what's going on without the bang?</div><div><br></div><div>I guess I'm just building up a bunch of thunks w/that <font face="monospace, monospace">Map.insertWith</font> call, but what kind of thunks? Unevaluated calls to <font face="monospace, monospace">splitOn</font> and (!!) and <font face="monospace, monospace">read</font> and (+) and <font face="monospace, monospace">lines</font>?</div><div><br></div><div>I thought a strict Map would avoid that.  I guess WHNF isn't enough?  Looking at <a href="https://wiki.haskell.org/Weak_head_normal_form" target="_blank">https://wiki.haskell.org/Weak_head_normal_form</a>, I don't <i>think</i> I have any constructors in there, but profiling with -hd shows me that (:) is the most frequently occurring closure. Where is <i>that</i> coming from?  Is the occurrence of (:) so high because it's either a built-in function applied to too few arguments or a lambda abstraction? Which one?  (Also, is "lambda abstraction" the same as "lambda expresson"?)</div><div><br></div><div>And then... what does that bang on the map argument do?  Does it force evaluation of the passed argument all the way down to primitives, so that we truly get a data structure containing only strings and ints (and no thunks)?  What does that do to time complexity?  Does it have to traverse the entire map looking for thunks, even though I only added one at some random location in the map?</div><div><br></div><div>Is there a better way?</div><div><br></div><div>I guess I need to force strictness somewhere else, but I'm not sure how.  I tried using <font face="monospace, monospace">seq </font>(a little half-heartedly), and ($!), but I guess I did it wrong and only wound up with more thunks to <font face="monospace, monospace">seq</font> and <font face="monospace, monospace">id ($!)</font>, right?  So, I wound up with lazy strictness?</div><div><br></div><div>Thanks for any help.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>John.</div></font></span></div>
</div><br></div>