A bug in IntMap

[Malcolm Wallace]

"Simon Peyton-Jones" <simonpj at microsoft.com> writes:

> Christian posted a bug to Sourceforge concerning the IntMap library,
> function split.
> 
> Can anyone shed any light?  Better still, fix it?

I consider the best approach for a bug like this is to use QuickCheck
to find a small failing case, then Hat to discover the cause of the
failure.  The first part was easy, but unfortunately the library
Data.IntMap does not yet have a traced version within Hat.  So,
I have a clearer formulation of the problem, but no solution yet.

In the meantime,

> "keys $ split 5 $ theMap" sometimes returns values greater 5. 

I think you probably mean

   keys $ fst $ split 5 $ theMap

And a failing case is the map

   {0:=1,1:=0,2:=0,3:=1,6:=-1,7:=0,8:=-2,9:=-2}

which you can generate with e.g.

   theMap = (insert 0 1 . insert 1 0 . insert 2 0 . insert 3 1 . insert 6 (-1)
            . insert 7 0 . insert 8 (-2) . insert 8 (-2))
            empty

The result of split 5 myMap is

   ({0:=1,1:=0,2:=0,3:=1,6:=-1}, {7:=0,8:=-2})

where clearly the mapping for 6 is in the wrong half of the result.

Regards,
    Malcolm