Opened 11 years ago

Closed 10 years ago

Last modified 46 years ago

#374 closed bug (Fixed)

IntMap.split wrong split

Reported by: nobody Owned by: nobody
Priority: normal Milestone:
Component: hslibs/data Version: 6.4
Keywords: Cc:
Operating System: Architecture:
Type of failure: Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


"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) 
[email protected]  

Change History (4)

comment:1 Changed 11 years ago by nobody

Logged In: NO 

Of course, it is with (fst) (and the Intmap contains more  
than one element, three in my case)  
"keys $ fst $ split 5 $ theMap"  

comment:2 Changed 10 years ago by pkturner

Logged In: YES 

Thanks to a simple reproduction of the bug by Malcolm
Wallace, I was able to track it down. 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
        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
          | 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 
        Tip ky y

comment:3 Changed 10 years ago by simonpj

Logged In: YES 

Fixed by Scott Turner and Malcolm Wallace

comment:4 Changed 10 years ago by simonpj

  • Status changed from assigned to closed
Note: See TracTickets for help on using tickets.