Ticket #2359 (closed bug: fixed)

Opened 1 year ago

Last modified 10 months ago

Data.IntMap update{Min,Max}WithKey corrupts data structure

Reported by: nwf Assigned to: simonmar
Priority: high Milestone: 6.10.1
Component: libraries/base Version: 6.8.2
Severity: normal Keywords:
Cc: Difficulty: Unknown
Test Case: Operating System: Linux
Architecture: x86_64 (amd64)

Description

Updates on the supposedly minimum element aren't:

GHCi, version 6.8.2: http://www.haskell.org/ghc/  :? for help
Loading package base ... linking ... done.
Prelude> import Data.IntMap
Prelude Data.IntMap> let base = (insert 2 "b" (singleton 1 "a"))
Loading package array-0.1.0.0 ... linking ... done.
Loading package containers-0.1.0.1 ... linking ... done.
Prelude Data.IntMap> let umin = updateMinWithKey (\ k _ -> ("yo!" ++ (show k)) ) base
Prelude Data.IntMap> umin
fromList [(1,"a"),(2,"yo!2")]
Prelude Data.IntMap> showTree umin
"*\n+-- 1:=\"a\"\n+-- 2:=\"yo!2\"\n"

Updates on the maximum element are even worse, corrupting the data structure (ghci session continued):

Prelude Data.IntMap> let umax = updateMaxWithKey (\ k _ -> ("yo!" ++ (show k)) ) base
Prelude Data.IntMap> umax
fromList [(1,"yo!1"),(1,"a")]
Prelude Data.IntMap> showTree umax
"*\n+-- 1:=\"yo!1\"\n+-- 1:=\"a\"\n"

GHC is Debian 6.8.2-5.

Anything else that would be helpful? Thanks much in advance.

Attachments

patch.txt (2.4 kB) - added by sedillard on 07/03/08 22:46:29.
fixed typos and added quickcheck test

Change History

06/14/08 12:20:56 changed by igloo

  • priority changed from normal to high.
  • difficulty set to Unknown.
  • milestone set to 6.10.1.

Thanks for the report.

It would be very useful if someone could put the datatype invariants as comments in the code.

07/03/08 22:46:29 changed by sedillard

  • attachment patch.txt added.

fixed typos and added quickcheck test

07/03/08 22:50:16 changed by sedillard

The problem was a typo, probably from cutting and pasting. I don't think more illuminating comments would have helped. A proper test, on the other hand...

09/02/08 08:54:11 changed by simonmar

  • owner set to simonmar.

Looks ok to me; I'll validate & commit.

09/09/08 08:55:11 changed by simonmar

  • status changed from new to closed.
  • resolution set to fixed.

Patch applied, thanks!

Thu Jul  3 22:43:50 PDT 2008  sedillard@gmail.com
  * Fixed typo in updateMinWithKey / updateMaxWithKey