Repository navigation
IntBinarySet's union, intersection, and difference functions do not work correctly #310
Description
Version
2025.1 (latest)
Operating System
- Any
- Linux
- macOS
- Windows
- Other Unix
OS Version
No response
Processor
- Any
- Arm (native)
- Arm (using Rosetta)
- x86-64
- Other
System Component
SML/NJ Library
Severity
Major
Description
IntBinarySet's union function adds multiple duplicates to the resulting set and the resulting sets are not ordered. Intersection sometimes does not return values that are in both sets, and difference doesn't return a set with the values in the second set removed from the first set, and actually adds more duplicate elements to the first set. Because of this, any code using IntBinarySet's union, intersection, or difference functions cannot be expected to work correctly.
Transcript
Standard ML of New Jersey [Version 2025.1; 64-bit; February 14, 2025]
- val set1 = IntBinarySet.singleton 5356;
val set1 = - : IntBinarySet.set
- val set2 = IntBinarySet.fromList [4986, 5360, 5361];
val set2 = - : IntBinarySet.set
- val set3 = IntBinarySet.union (set1, set2);
val set3 = - : IntBinarySet.set
- IntBinarySet.listItems set3;
val it = [4986,5356,4986,5360,5361] : IntBinarySet.item list
- val set4 = IntBinarySet.union (IntBinarySet.singleton 5358, set3);
val set4 = - : IntBinarySet.set
- IntBinarySet.listItems set4;
val it = [4986,5356,4986,5358,4986,5360,5361] : IntBinarySet.item list
- IntBinarySet.intersection (IntBinarySet.singleton 4986, set4);
val it = - : IntBinarySet.set
- IntBinarySet.listItems it;
val it = [4986,4986,4986] : IntBinarySet.item list
- IntBinarySet.intersection (IntBinarySet.singleton 5360, set4);
val it = - : IntBinarySet.set
- IntBinarySet.listItems it;
val it = [] : IntBinarySet.item list
- IntBinarySet.difference (set4, IntBinarySet.singleton 5360);
val it = - : IntBinarySet.set
- IntBinarySet.listItems it;
val it = [4986,5356,4986,5358,4986,4986,5356,4986,5358,4986,5360,5361]Expected Behavior
Union should not add duplicate elements out of order into the set. Intersection between {4986,5356,5358,5360,5361} and {5360} should not return an empty set. Difference should remove 5360 from {4986,5356,5358,5360,5361}, but instead it adds a whole bunch of extra duplicate elements out of order.
Steps to Reproduce
Loading a file with this code in the REPL:
structure Main =
struct
val showSet = fn t0 =>
"["
^ String.concatWith ", " (List.map Int.toString (IntBinarySet.listItems t0))
^ "]"
fun run () =
let
val set1 = IntBinarySet.singleton 5356
val set2 = IntBinarySet.fromList [4986, 5360, 5361]
val set3 = IntBinarySet.union (set1, set2)
val set4 = IntBinarySet.union (IntBinarySet.singleton 5358, set3)
val set5 = IntBinarySet.intersection (IntBinarySet.singleton 5360, set4)
val set6 = IntBinarySet.difference (set4, IntBinarySet.singleton 5360)
in
print ("Set3: " ^ showSet set3 ^ "\n");
print ("Set4: " ^ showSet set4 ^ "\n");
print ("Set5: " ^ showSet set5 ^ "\n");
print ("Set6: " ^ showSet set6 ^ "\n")
end
endand calling Main.run (); prints:
Set3: [4986, 5356, 4986, 5360, 5361]
Set4: [4986, 5356, 4986, 5358, 4986, 5360, 5361]
Set5: []
Set6: [4986, 5356, 4986, 5358, 4986, 4986, 5356, 4986, 5358, 4986, 5360, 5361]
Whereas it should print:
Set3: [4986, 5356, 5360, 5361]
Set4: [4986, 5356, 5358, 5360, 5361]
Set5: [5360]
Set6: [4986, 5356, 5358, 5361]
Additional Information
No response
Activity
JohnReppy commentedon Jul 17, 2025
Fixed by pull request #308.
[-]IntBinarySet's `union`, `intersection`, and `difference` functions do not work correctly[/-][+]`IntBinarySet`'s `union`, `intersection`, and `difference` functions do not work correctly[/+]ci(nix): build with modern MLton (nixpkgs `mlton`, 20241230) instead …
Move urweb to modern MLton (20241230) via smlnj-lib IntBinarySet work…