Search code examples
haskellset-difference

Is there a difference Ord operator on lists in haskell?

I would like to do set difference between 2 integer lists, which allow repetitions in haskell.

So in case of having [1,2,1,4,3] [1,2,4], the difference would be [1,3]

Currently I can do it via the normal \\ operator listA \\ listB.

But the problem is this too slow. As integers are in ord group it can be done faster.

I am aware of the Data.Multiset module, which would do it faster, but is there a native way to do it on lists without the Data.Multiset module?

Solution

  • As integers are in ord group it can be done faster.

    Yes, but it requires building a sorted index. And that's pretty much what Data.Multiset is doing. You could of course write an operation that does that manually, but you'd be effectively reimplementing Multiset by then.