[Haskell-cafe] Stack overflow

[Adrian Hey]

Bertram Felgenhauer wrote:
> I'm fairly certain that the stack overflow is (indirectly) caused by
> Data.Binary, not Data.Map.

Yes, I think you are right. At least it seems clear that the stack
overflow is not directly caused by fromDistinctAscList.

> The result of 'decode' is a list of known length with unevaluated
> elements (because the Get monad is lazy) [*], where each element depends
> on the previous one (because reading is sequential, and the elements of
> the list may have nonuniform size). Now when you evaluate the last
> element, that will demand the last but one element, which in turn will
> demand the previous element, and so on. If the list is long enough,
> you'll get a stack overflow.
> 
> Using fromAscList instead of fromDistinctAscList cures the problem,
> because it inspects every key in the list, starting from the beginning,
> in order to eliminate duplicates. fromDistinctAscList, on the other
> hand, does not inspect the keys at all.
> 
>    do
>     [path] <- getArgs
>     m <- liftM decode (BS.readFile path)::IO [((Int, Maybe String), Int)]
>     putStrLn . show . last $ m
> 
> should also exhibit the same stack overflow.

Indeed it does. So it seems if I understand correctly, this is yet
another example what I would call the lazy applied strict thunk chain
problem (I'm sure you understand what I mean by that).

The standard "party line" advice in such circumstances is to prevent
their formation by evaluating eagerly as they are applied. However,
this is often not possible for users of libraries they don't "own",
if the API does not provide the necessary strictness control. I would
argue that even if it possible is sometimes undesirable too (if
evaluation is expensive, saves nothing in heap use and the final
value may never be needed).

So I still think the stack management system should be designed so
that as far as is practical (given finite memory), any expression
that can be built on the heap can also be evaluated without causing
a "stack overflow".

But I guess this rant is not much help to the OP :-)

Regards
--
Adrian Hey