[Haskell] stack overflow - nonobvious thunks?

Scherrer, Chad Chad.Scherrer at pnl.gov
Wed Jul 27 13:12:45 EDT 2005

I'm trying to write a function to build a table of values from a list.
Here's my current attempt:

table :: (Ord a) => [a] -> [(a,Int)]
table xs = Map.assocs $! foldl' f Map.empty xs
    f m x = Map.insertWith (+) x 1 m

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

unif :: [Int]
unif = randomRs (1,10) $ mkStdGen 1

then I should be able to use

f :: Int -> [(Int, Int)]
f n = table $ take n unif

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)

*Main> f 1000000
*Main> f 10000000
[(1,*** Exception: stack overflow

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?

Chad Scherrer
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org//pipermail/haskell/attachments/20050727/f2006354/attachment.htm

More information about the Haskell mailing list