Use Ord by default for nub, difference, etc

[hdgarrood]

Currently we use an Eq constraint for functions like nub and difference. However this gives a poor asymptotic complexity; see https://github.com/nh2/haskell-ordnub.

Of course, there are some types which have Eq but not Ord instances so it makes sense to make Eq versions of these functions available. However, most types do have Ord instances so I think the default version should use Ord. That is, I'd prefer to have nub :: forall a. Ord a => Array a -> Array a and additionally nubEq which is the same except with only an Eq constraint.

This is a little bit difficult with respect to dependencies because we would probably want to depend on sets to do this, but maps (which is a dependency of sets) already depends on arrays. So that's one issue to sort out, if we do agree that we want to do this.

[borsboom]

nub is such a common source of accidental performance problems in Haskell code, so I'm very much +1 on this. The extra package's implementation of nubOrd doesn't depend on sets or maps.

[matthewleon]

This is a little bit difficult with respect to dependencies because we would probably want to depend on sets to do this, but maps (which is a dependency of sets) already depends on arrays. So that's one issue to sort out, if we do agree that we want to do this.

I think this is another reason in favor of purescript-deprecated/purescript-sets#46

[matthewleon]

On further thought, it's not clear to me that Set is necessary, or beneficial, to do this. We could use Array's own sort, which uses FFI to the JS engine's native Array.sort, and do nub the imperative way. It would avoid the extra dep, and also quite possibly be faster.

[matthewleon]

I've taken a shot at nub here: #128

[hdgarrood]

Currently nub preserves order, though, ie nub xs == xs when xs has no duplicates. If I understand correctly your implementation doesn’t have this property. I think it’s a useful property, though, and so I’d rather not lose it.

[garyb]

Resolved in the 0.12 branch