Is there a more-robust FiniteMap?

23 Feb 2002

      Using FiniteMap, I often run into robustness problems.  For example,
consider the following program, which illustrates a common problem:

    module Main (main) where
    import FiniteMap

    main = print
         . last
         . fmToList
         . listToFM
         $ [(i,()) | i <- [0..100000]]

When compiled with ghc-5.02.2-1 on Red Hat Linux 6.2

    $ ghc --make -package data -O2 -o test5 test5

and executed, the program quickly dies:

    $ ./test5
    Stack space overflow: current size 1048576 bytes.
    Use `+RTS -Ksize' to increase it.

Similarly, under hugs:

    $ hugs -h10M
    __   __ __  __  ____   ___      _________________________________________
    ||   || ||  || ||  || ||__      Hugs 98: Based on the Haskell 98 standard
    ||___|| ||__|| ||__||  __||     Copyright (c) 1994-2001
    ||---||         ___||           World Wide Web: http://haskell.org/hugs
    ||   ||                         Report bugs to: hugs-bugs@haskell.org
    ||   || Version: December 2001  _________________________________________

    Haskell 98 mode: Restart with command line option -98 to enable extensions

    Reading file "/usr/share/hugs/lib/Prelude.hs":

    Hugs session for:
    /usr/share/hugs/lib/Prelude.hs
    Type :? for help
    Prelude> :load test5.hs
    Reading file "test5.hs":
    Reading file "/usr/share/hugs/lib/exts/FiniteMap.lhs":
    Reading file "/usr/share/hugs/lib/Maybe.hs":
    Reading file "/usr/share/hugs/lib/exts/FiniteMap.lhs":
    Reading file "test5.hs":

    Hugs session for:
    /usr/share/hugs/lib/Prelude.hs
    /usr/share/hugs/lib/Maybe.hs
    /usr/share/hugs/lib/exts/FiniteMap.lhs
    test5.hs
    Main> main

    Segmentation fault (core dumped)

This leaves a 90-MB core file, not exactly the output I was expecting!
;-)

Looking through the FiniteMap sources, one sees that foldl-like
behavior is at the heart of both listToFM and fmToList, not to mention
many other FiniteMap favorites.  Doesn't this make these functions --
and perhaps FiniteMap itself -- stack hungry and generally unreliable
for large sets of data?

Please help me understand the underlying issues better.  Maybe
FiniteMap is fine as it is, and I'm just doing something wrong.
Should I be providing better strictness hints to the compiler?  Am I
using FiniteMap in a manner for which it wasn't intended?  Should I
write application-specific versions of FiniteMap for particular uses?
Or is there an industrial-strength FiniteMap that I can rely on for
all purposes?

Thanks in advance for any hints, tips, and wisdom that you can share.

Cheers,
Tom

Is there a more-robust FiniteMap?

Tom Moertel