search

Abhiroop / okasaki

A Haskell Collections library. [WIP]
BSD 3-Clause "New" or "Revised" License
15 stars 3 forks source link

Bug in red-black tree code #1

Closed danidiaz closed 5 years ago

danidiaz commented 5 years ago

Hi,

There seems to be a bug in the code for the red-black-tree. For example, this causes an exception:

delete "foo" (insert "foo" (insert "bar" E)) *** Exception: Main.hs:(84,1)-(87,59): Non-exhaustive patterns in function balR

Abhiroop commented 5 years ago

Thanks for reporting. https://github.com/Abhiroop/okasaki/commit/292601deb36ea57e080524275dd1c090de15e27f should fix this.

It was extremely hard to track and fix this minute bug. Took me a couple of hours. If people actually intend to use this, I should add Quickcheck tests for it. Also I should add that this implementation is actually a Set rather than a Tree. I basically added a delete functionality to the Red Black Tree backed Set demonstrated in Okasaki.

danidiaz commented 5 years ago

I'm not using the code as-is, but i'm using it as an inspiration and that bug cropped up. Thanks for the fix!

Abhiroop commented 5 years ago

Closing this as https://github.com/Abhiroop/okasaki/commit/292601deb36ea57e080524275dd1c090de15e27f fixes this.