Dear library folk, Christian posted a bug to Sourceforge concerning the IntMap library, function split. Can anyone shed any light? Better still, fix it? Simon and I have too many other bugs to nail for 6.4.1 thanks Simon http://sourceforge.net/tracker/index.php?func=detail&aid=1195579&group_i d=8032&atid=108032 "keys $ split 5 $ theMap" sometimes returns values greater 5. I am still trying to pinpoint the bug, but since it shows itself only deep inside a complicated structure, I have problems doing so. One pointer might be, that my values are partially evaluated functions, but this is only a guess. (Changing the data structure to Data.Map restores normal operation in my algorithm)
"Simon Peyton-Jones"
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
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.
Another bunch of interesting results for split, showing a significant number of off-by-one bugs: split 4 {6:=0,7:=0} = ({}, {6:=0,7:=0}) split 5 {6:=0,7:=0} = ({6:=0}, {7:=0}) split 6 {6:=0,7:=0} = ({}, {7:=0}) split 7 {6:=0,7:=0} = ({6:=0}, {}) split 8 {6:=0,7:=0} = ({6:=0}, {7:=0}) split 9 {6:=0,7:=0} = ({6:=0,7:=0}, {}) Regards, Malcolm
The bug is right there in split. Data/IntMap.hs needs: *************** *** 750,755 **** --- 750,756 ---- split k t = case t of Bin p m l r + | nomatch k p m -> if k>p then (t,Nil) else (Nil,t) | zero k m -> let (lt,gt) = split k l in (lt,union gt r) | otherwise -> let (lt,gt) = split k r in (union l lt,gt) Tip ky y *************** *** 764,769 **** --- 765,771 ---- splitLookup k t = case t of Bin p m l r + | nomatch k p m -> if k>p then (t,Nothing,Nil) else (Nil,Nothing,t) | zero k m -> let (lt,found,gt) = splitLookup k l in (lt,found,union gt r) | otherwise -> let (lt,found,gt) = splitLookup k r in (union l lt,found,gt) Tip ky y
Scott Turner wrote:
The bug is right there in split. Data/IntMap.hs needs:
Ha, great that you found it so fast! Thanks a lot, -- Daan Leijen.
*************** *** 750,755 **** --- 750,756 ---- split k t = case t of Bin p m l r + | nomatch k p m -> if k>p then (t,Nil) else (Nil,t) | zero k m -> let (lt,gt) = split k l in (lt,union gt r) | otherwise -> let (lt,gt) = split k r in (union l lt,gt) Tip ky y *************** *** 764,769 **** --- 765,771 ---- splitLookup k t = case t of Bin p m l r + | nomatch k p m -> if k>p then (t,Nothing,Nil) else (Nil,Nothing,t) | zero k m -> let (lt,found,gt) = splitLookup k l in (lt,found,union gt r) | otherwise -> let (lt,found,gt) = splitLookup k r in (union l lt,found,gt) Tip ky y _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries
participants (4)
-
Daan Leijen -
Malcolm Wallace -
Scott Turner -
Simon Peyton-Jones