[Haskell] performance tuning Data.FiniteMap

[Johannes Waldmann]

S. Alexander Jacobson wrote:
> Does FiniteMap used Arrays, Lists, or Algebraic Types?

when in doubt, RTFC:

http://cvs.haskell.org/cgi-bin/cvsweb.cgi/fptools/libraries/base/Data/FiniteMap.hs?rev=1.17


data FiniteMap key elt
   = EmptyFM
   | Branch key elt	    	-- Key and elt stored here
     IF_GHC(Int#,Int{-STRICT-})	-- Size >= 1
     (FiniteMap key elt)	    	-- Children
     (FiniteMap key elt)


the hugs distribution even says where this comes from:

This code is derived from that in the paper:
\begin{display}
         S Adams
         "Efficient sets: a balancing act"
         Journal of functional programming 3(4) Oct 1993, pp553-562
\end{display}



-- 
-- Johannes Waldmann,  Tel/Fax: (0341) 3076 6479 / 6480 --
------ http://www.imn.htwk-leipzig.de/~waldmann/ ---------