[Haskell] stack overflow - nonobvious thunks?

[Scherrer, Chad]

Adrian, Does your AVL library have an "insertWith'"-type function
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 
http://users.aber.ac.uk/afc/stricthaskell.html

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.

-Chad

-----Original Message-----
From: u.stenzel at web.de [mailto:u.stenzel at web.de] 
Sent: Wednesday, July 27, 2005 11:02 AM
To: Scherrer, Chad
Cc: haskell at haskell.org
Subject: Re: [Haskell] stack overflow - nonobvious thunks?

Scherrer, Chad wrote:
 
>     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