[Haskell-cafe] Stack overflow

[Adrian Hey]

Philip Armstrong wrote:
> Since no-one else has answered, I'll take a stab.
> Obiously, you have a stack leak due to laziness somewhere

I wouldn't say that was obvious, though it is certainly a
possibility.

I'm never exactly clear what people mean by a "stack leak".
It seems some folk regard any algorithm that makes use of
O(n) or worse stack space as a "stack leak".

My opinion is that using O(n) or worse working memory when
the job could be done in O(log n) or O(1) memory is certainly
bad, but using O(n) stack is no worse in principle than using
O(n) heap. But at the moment it is worse in practice with ghc,
regretably :-(

> In fact, a little experimentation has revealed that this:
> 
>   do
>    [path] <- getArgs
>    m <- liftM decode (BS.readFile path)::IO [((Int, Maybe String), Int)]
>    putStrLn . show . findMax . fromAscList $ m
> 
> will work just fine. No extra evaluation needed at all! I'll leave it
> to the Haskell gurus to explain what's going on...

That's very interesting. Strangely if you use fromDistinctAscList
instead (as used by the Binary instance get method) the problem
re-appears. This is despite fromAscList making use of fromDistinctAscList.

BTW, I find this especially ironic as fromDistinctAscList is the perfect
example what I was talking about in another thread (continuation passing
madness caused by an irrational fear of stack use).

As to what's really going on here, I haven't figured it out and I'm not
really inclined to try :-)

Regards
--
Adrian Hey