Faster `elem` "Hack" for Data.Set?

[Viktor Dukhovni]

On Sat, Jan 29, 2022 at 07:59:51PM -0500, David Feuer wrote:

> One is that `containers` has a long history of attempting to remain
> compatible with potential future Haskell 98-like Haskell
> implementations (likely with a few days of work to patch up mistakes
> when the time comes).  Using a GADT to define Set would break that
> quite thoroughly.

Yes, that's definitely an issue.

> My second concern is more practical:
> 
>   type Set a = SetImpl a a
> 
> is all sorts of problematic. It forces anyone who wants to use what's
> always been the `Set` type constructor (Set :: Type -> Type) to dig
> into the implementation and use `SetImpl :: Type -> Type -> Type`
> instead. That's quite a different beast.

Well, they could use the unsaturated type alias in some cases, but
there are likely situations where that's not an option.

> I don't know all the things that will break, but they'll surely
> include
> <https://hackage.haskell.org/package/constrained-monads-0.5.0.0/docs/Control-Monad-Constrained.html>.

Yes, that would break irreperably

> I think the real answer is to remove `elem` from `Foldable` and put it
> somewhere more appropriate.

Perhaps so, though my guess is that this is unlikely to happen...

Overall, your objections are likely sufficient.

-- 
    Viktor.