[Haskell-cafe] Stack overflow

[Bertram Felgenhauer]

Adrian Hey wrote:
> Philip Armstrong wrote:
>> 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).

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

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.

HTH,

Bertram

[*] For example, consider this:
    Prelude Data.Binary> length (decode (encode (42 :: Int)) :: [Int])
    42
    Prelude Data.Binary> decode (encode (42 :: Int)) :: [Int]
    [*** Exception: too few bytes. Failed reading at byte position 16