# [Haskell] stack overflow - nonobvious thunks?

Dean Herington heringtonlacey at mindspring.com
Thu Jul 28 02:27:13 EDT 2005

```The following version seems to do the trick (and still remain quite
readable).  It worked for 100000000 as well.

import Data.Map as Map
import System.Random
import Data.List (foldl')

table :: (Ord a) => [a] -> [(a,Int)]
table xs = Map.assocs \$! foldl' f Map.empty xs
where f m x = let  m' = Map.insertWith (+) x 1 m
Just v = Map.lookup x m'
in v `seq` m'

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

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

main = print \$ f 10000000

- Dean

At 2:19 PM -0700 7/27/05, Scherrer, Chad wrote:
>mentioned by Udo?
>
>If I lookup and insert into the table separately, forcing evaluation at
>each step, I can do
>
>table' :: (Ord a) => [a] -> [(a, Int)]
>table' xs = Map.assocs \$! foldl' f Map.empty xs
>     where
>     f m x = (Map.insert x \$! 1 + Map.findWithDefault 0 x m) \$! m
>
>This helps with the stack overflow problem, but now I'm hitting a
>different wall:
>
>*Main> table \$ take 10000000 unif
>[(1,999662),(2,1000220),(3,998800),(4,1000965),(5,999314),(6,1001819),(7
>,1000997),(8,999450),(9,999877),(10,998896)]
>
>*Main> table \$ take 100000000 unif
><interactive>: out of memory (requested 1048576 bytes)
>
>I thought I may have found a good approach using an idea from one of
>Amanda Clare's pages
>
>If I write
>
>eqSeq x y = if x==x then y else y
>
>this forces evaluation of x further than seq alone. Then I can write
>
>table :: (Ord a) => [a] -> [(a, Int)]
>table xs = Map.assocs \$! foldl' f Map.empty xs
>     where
>     f m x = m `eqSeq` Map.insertWith (+) x 1 m
>
>Same result as Udo's suggestion - out of memory.
>
>I still don't see why this function should need any more than a few
>kilobytes, even for very large n like this.
>
>
>-----Original Message-----
>From: u.stenzel at web.de [mailto:u.stenzel at web.de]
>Sent: Wednesday, July 27, 2005 11:02 AM
>Subject: Re: [Haskell] stack overflow - nonobvious thunks?
>
>
>>      f m x = Map.insertWith (+) x 1 m
>
>insertWith is inserting the "nonobvious thunks".  Internally it applies
>(+) to the old value and the new one, producing a thunk.  There is no
>place you could put a seq or something to force the result.  You
>basically need insertWith', which isn't there.
>
>I think, your best best is to manually lookup the old value, combine
>with the new, force the result, then insert that, overwriting the old
>value.
>
>On top of that you still need foldl' to avoid building long chains of
>Map.insert.
>
>
>Udo.
>--
>The Second Law of Thermodynamics:
>         If you think things are in a mess now, just wait!
>	                -- Jim Warner
>_______________________________________________