[ ghc-Bugs-1195579 ] IntMap.split wrong split

[SourceForge.net]

Bugs item #1195579, was opened at 2005-05-04 19:18
Message generated for change (Comment added) made by pkturner
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=108032&aid=1195579&group_id=8032

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: hslibs/data
Group: 6.4
Status: Open
Resolution: None
Priority: 5
Submitted By: Nobody/Anonymous (nobody)
Assigned to: Nobody/Anonymous (nobody)
Summary: IntMap.split wrong split

Initial Comment:
"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) 
 
Christian  
  
choener at cebitec.uni-bielefeld.de  
  

----------------------------------------------------------------------

Comment By: Scott Turner (pkturner)
Date: 2005-07-06 12:03

Message:
Logged In: YES 
user_id=22153

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
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

----------------------------------------------------------------------

Comment By: Nobody/Anonymous (nobody)
Date: 2005-05-04 19:21

Message:
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"  
  
Christian 
choener at ... 

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=108032&aid=1195579&group_id=8032