Opened 12 years ago

Closed 12 years ago

# IntMap.split wrong split

Reported by: Owned by: nobody nobody normal hslibs/data 6.4 None/Unknown

### Description

```"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@cebitec.uni-bielefeld.de

```

### comment:1 Changed 12 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"

Christian
choener@...
```

### comment:2 Changed 12 years ago by pkturner

```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:3 Changed 12 years ago by simonpj

```Logged In: YES
user_id=50165

Fixed by Scott Turner and Malcolm Wallace
```

### comment:4 Changed 12 years ago by simonpj

Status: assigned → closed
Note: See TracTickets for help on using tickets.