Use Ord by default for all set-like operations

[hdgarrood]

We already made nub use Ord by default in #91, but there are a few other unnecessarily quadratic functions in this library still which probably deserve the same treatment. I think these are union, intersect, and difference.

As well as being quadratic, union and difference have a strange-seeming behaviour where duplicates are only preserved in the first argument:

union [0, 0] [1, 1] == [0, 0, 1]

See #56 for more info. We ought to be careful about changing this behaviour but I think we should consider it, since I think it’s very likely to trip people up and we will be making breaking changes to these functions anyway if we do this.

[hdgarrood]

If we go ahead with this, the same changes should propagate through to the lists library too.

[milesfrain]

duplicates are only preserved in the first argument

Yes, this seems really strange, even if it does match how things are done in Haskell. I'm curious if any projects rely on this asymmetric duplicate-preserving behavior.

If we match Set behavior and remove all duplicates, then we get simpler code (just append then nub), and we can do property-based testing against Set.

Another option is to thin-out these libraries a bit and recommend using Set instead. Potential downsides are inconvenience, loss of ordering, and worse performance (would be interesting to benchmark). And we'd still need the Ord-free versions, since those aren't Set-compatible.

Perhaps we should open a discourse thread to discuss these proposals, since this affects multiple libraries.

[hdgarrood]

The main reason I don't really want to just deprecate these functions and tell people to just use sets instead is that arrays have ordering, whereas sets don't, which means that the set-like Array/List operations can preserve ordering, and this might be useful in some cases.

[JordanMartinez]

This is the last issue in this repo that doesn't currently have a PR opened for it.

[milesfrain]

I'm thinking we should table all these container (List, Array, etc.) updates for 0.15.
I think it would be more efficient to do a systematic update of all our container libraries, where we start with a proposal of what we want our final result to be, rather than through a bunch of piecemeal PRs.

[JordanMartinez]

A few questions I have.

First, how is union different from <|>?

Second, in the following examples of difference/\\, what should the output be?

[1, 2, 3, 4, 3, 2] \\ [1]
-- I assume [2, 3, 4, 3, 2]

[1, 2, 3, 4, 3, 2] \\ [2]
[1, 2, 3, 4, 3, 2] \\ [2, 2]
-- It depends on whether each 2 in the right array
-- removes only one or all 2 element(s) in the left array

[milesfrain]

how is union different from <|>?

union does a set-like union of the two arrays. <|> is the same as append/<>.
union keeps any duplicates that already exist in the first array and removes duplicates from the second array. Keeping these duplicates seems like the lesser-of-evils, since you're forced to break one of these rules when applying set operations on non-sets:

a union b == b union a  -- we break this rule
a union empty == a      -- we follow this rule
a union a == a          -- we follow this rule
a union (a <> a) == a   -- we follow this rule

I think difference behaves reasonably for arrays too, but it's still somewhat of an imperfect set-like operation.

Example input/output:

  logShow $ union [1,2,3,3] [2,2,4,4]
  logShow $ [1,2,3,3] <|> [2,2,4,4]
  logShow $ [1,2,3,3] <> [2,2,4,4]
  logShow $ [1, 2, 3, 4, 3, 2] \\ [1]
  logShow $ [1, 2, 3, 4, 3, 2] \\ [2]
  logShow $ [1, 2, 3, 4, 3, 2] \\ [2, 2]

[1,2,3,3,4]
[1,2,3,3,2,2,4,4]
[1,2,3,3,2,2,4,4]
[2,3,4,3,2]
[1,3,4,3,2]
[1,3,4,3]

https://try.ps.ai/?gist=aea5bdaf7669d2fd00c8d80cecc01b38

[milesfrain]

The main reason I don't really want to just deprecate these functions and tell people to just use sets instead is that arrays have ordering, whereas sets don't, which means that the set-like Array/List operations can preserve ordering, and this might be useful in some cases.

I think an ordered set would be even better. http://hackage.haskell.org/package/ordered-containers-0.2.2/docs/Data-Set-Ordered.html
But no objections to keeping the set-like operations for arrays.

[JordanMartinez]

ordered set would be even better.

Isn't better subjective to the problem one is solving?

[milesfrain]

Better if we assume these requirements:

• maintain ordering
• not having any weirdness with set-like operations

Of course, there can be other requirements, but I didn't see anything else mentioned.

[JordanMartinez]

a union b == b union a  -- we break this rule
a union empty == a      -- we follow this rule
a union a == a          -- we follow this rule
a union (a <> a) == a   -- we follow this rule

logShow $ union [1,2,3,3] [2,2,4,4]

Thanks @milesfrain. These examples helped! Pretty sure #203 is ready to go now.