Description
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.