<!doctype html public "-//W3C//DTD W3 HTML//EN">
<html><head><style type="text/css"><!--
blockquote, dl, ul, ol, li { padding-top: 0 ; padding-bottom: 0 }
 --></style><title>RE: [Haskell] stack overflow - nonobvious
thunks?</title></head><body>
<div>The following version seems to do the trick (and still remain
quite readable).&nbsp; It worked for 100000000 as well.</div>
<div><br></div>
<div><font face="Courier">import Data.Map as Map<br>
import System.Random<br>
import Data.List (foldl')<br>
<br>
table :: (Ord a) =&gt; [a] -&gt; [(a,Int)]<br>
table xs = Map.assocs $! foldl' f Map.empty xs<br>
&nbsp;&nbsp;&nbsp; where f m x = let&nbsp; m' = Map.insertWith (+) x 1
m<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span
></span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
Just v = Map.lookup x m'<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span
></span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; in v `seq` m'<br>
<br>
unif :: [Int]<br>
unif = randomRs (1,10) $ mkStdGen 1<br>
<br>
f :: Int -&gt; [(Int, Int)]<br>
f n = table $ take n unif</font><br>
<font face="Courier"></font></div>
<div><font face="Courier">main = print $ f 10000000</font></div>
<div><br></div>
<div>- Dean</div>
<div><br></div>
<div><br></div>
<div>At 2:19 PM -0700 7/27/05, Scherrer, Chad wrote:</div>
<blockquote type="cite" cite>Adrian, Does your AVL library have an
&quot;insertWith'&quot;-type function<br>
mentioned by Udo?<br>
<br>
If I lookup and insert into the table separately, forcing evaluation
at<br>
each step, I can do<br>
<br>
table' :: (Ord a) =&gt; [a] -&gt; [(a, Int)]<br>
table' xs = Map.assocs $! foldl' f Map.empty xs<br>
&nbsp;&nbsp;&nbsp; where<br>
&nbsp;&nbsp;&nbsp; f m x = (Map.insert x $! 1 + Map.findWithDefault 0
x m) $! m<br>
<br>
This helps with the stack overflow problem, but now I'm hitting a<br>
different wall:<br>
<br>
*Main&gt; table $ take 10000000 unif<br>
[(1,999662),(2,1000220),(3,998800),(4,1000965),(5,999314),(6,1001819)<span
></span>,(7<br>
,1000997),(8,999450),(9,999877),(10,998896)]<br>
<br>
*Main&gt; table $ take 100000000 unif<br>
&lt;interactive&gt;: out of memory (requested 1048576 bytes)<br>
<br>
I thought I may have found a good approach using an idea from one
of<br>
Amanda Clare's pages<br>
http://users.aber.ac.uk/afc/stricthaskell.html<br>
<br>
If I write<br>
<br>
eqSeq x y = if x==x then y else y<br>
<br>
this forces evaluation of x further than seq alone. Then I can
write<br>
<br>
table :: (Ord a) =&gt; [a] -&gt; [(a, Int)]<br>
table xs = Map.assocs $! foldl' f Map.empty xs<br>
&nbsp;&nbsp;&nbsp; where<br>
&nbsp;&nbsp;&nbsp; f m x = m `eqSeq` Map.insertWith (+) x 1 m<br>
<br>
Same result as Udo's suggestion - out of memory.<br>
<br>
I still don't see why this function should need any more than a
few<br>
kilobytes, even for very large n like this.<br>
<br>
-Chad<br>
<br>
-----Original Message-----<br>
From: u.stenzel@web.de [mailto:u.stenzel@web.de]<br>
Sent: Wednesday, July 27, 2005 11:02 AM<br>
To: Scherrer, Chad<br>
Cc: haskell@haskell.org<br>
Subject: Re: [Haskell] stack overflow - nonobvious thunks?<br>
<br>
Scherrer, Chad wrote:<br>
&nbsp;<br>
&gt;&nbsp;&nbsp;&nbsp;&nbsp; f m x = Map.insertWith (+) x 1 m<br>
<br>
insertWith is inserting the &quot;nonobvious thunks&quot;.&nbsp;
Internally it applies<br>
(+) to the old value and the new one, producing a thunk.&nbsp; There
is no<br>
place you could put a seq or something to force the result.&nbsp;
You<br>
basically need insertWith', which isn't there.<br>
<br>
I think, your best best is to manually lookup the old value,
combine<br>
with the new, force the result, then insert that, overwriting the
old</blockquote>
<blockquote type="cite" cite>value.</blockquote>
<blockquote type="cite" cite><br></blockquote>
<blockquote type="cite" cite>On top of that you still need foldl' to
avoid building long chains of</blockquote>
<blockquote type="cite" cite>Map.insert.</blockquote>
<blockquote type="cite" cite><br></blockquote>
<blockquote type="cite" cite><br></blockquote>
<blockquote type="cite" cite>Udo.</blockquote>
<blockquote type="cite" cite>--</blockquote>
<blockquote type="cite" cite>The Second Law of
Thermodynamics:</blockquote>
<blockquote type="cite" cite>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
If you think things are in a mess now, just wait!<br>
<x-tab>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</x-tab
>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span
></span>&nbsp;&nbsp;&nbsp;&nbsp; -- Jim Warner<br>
_______________________________________________<br>
Haskell mailing list<br>
Haskell@haskell.org<br>
http://www.haskell.org/mailman/listinfo/haskell</blockquote>
<div><br></div>
</body>
</html>