<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=us-ascii">
<META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7232.77">
<TITLE>stack overflow - nonobvious thunks?</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/rtf format -->
<P><FONT SIZE=2 FACE="Arial">I'm trying to write a function to build a table of values from a list. Here's my current attempt:</FONT>
</P>
<P><FONT SIZE=2 FACE="Arial">table :: (Ord a) => [a] -> [(a,Int)]</FONT>
<BR><FONT SIZE=2 FACE="Arial">table xs = Map.assocs $! foldl' f Map.empty xs</FONT>
<BR><FONT SIZE=2 FACE="Arial"> where</FONT>
<BR><FONT SIZE=2 FACE="Arial"> f m x = Map.insertWith (+) x 1 m</FONT>
</P>
<P><FONT SIZE=2 FACE="Arial">The ($!) and the foldl' were my clumsy attempts to avoid the stack overflows I keep getting, but it's not working right yet. If I set</FONT></P>
<P><FONT SIZE=2 FACE="Arial">unif :: [Int]</FONT>
<BR><FONT SIZE=2 FACE="Arial">unif = randomRs (1,10) $ mkStdGen 1</FONT>
</P>
<P><FONT SIZE=2 FACE="Arial">then I should be able to use</FONT>
</P>
<P><FONT SIZE=2 FACE="Arial">f :: Int -> [(Int, Int)]</FONT>
<BR><FONT SIZE=2 FACE="Arial">f n = table $ take n unif</FONT>
</P>
<P><FONT SIZE=2 FACE="Arial">I would think this should work using very little memory, since unif is evaluated lazily, and the table is built eagerly. But I must be keeping around more thunks than I think, since I get (in ghci)</FONT></P>
<P><FONT SIZE=2 FACE="Arial">*Main> f 1000000</FONT>
<BR><FONT SIZE=2 FACE="Arial">[(1,99816),(2,100187),(3,99969),(4,99892),(5,100194),(6,100190),(7,99776),(8,100347),(9,100125),(10,99504)]</FONT>
<BR><FONT SIZE=2 FACE="Arial">*Main> f 10000000</FONT>
<BR><FONT SIZE=2 FACE="Arial">[(1,*** Exception: stack overflow</FONT>
</P>
<P><FONT SIZE=2 FACE="Arial">So it works on big lists, but not huge ones. What am I missing? Is there a way to do this other than just increasing the memory allocation?</FONT></P>
<P><FONT SIZE=2 FACE="Arial">Thanks,</FONT>
<BR><FONT SIZE=2 FACE="Arial">Chad Scherrer</FONT>
</P>
</BODY>
</HTML>