The `elem` method of `Foldable` is a poor abstraction for structures with faster than linear search

Motivation

The Foldable class generalises various operations from List (i.e. []) that are mostly inherently linear in the structure size, or (in the case of e.g. length) can be optimised to an O(1) operation for some structures.

Many of the methods carry no additional type constraints on the element type, or carry constraints that are natural (Num for sum and product, Monoid for fold, ...). If we look at the full method list, just one (elem) has a constraint that is not necessarily the natural one for every structure:

class Foldable t where
  Data.Foldable.fold :: Monoid m => t m -> m
  foldMap :: Monoid m => (a -> m) -> t a -> m
  Data.Foldable.foldMap' :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b
  Data.Foldable.foldr' :: (a -> b -> b) -> b -> t a -> b
  foldl :: (b -> a -> b) -> b -> t a -> b
  Data.Foldable.foldl' :: (b -> a -> b) -> b -> t a -> b
  foldr1 :: (a -> a -> a) -> t a -> a
  foldl1 :: (a -> a -> a) -> t a -> a
  Data.Foldable.toList :: t a -> [a]
  null :: t a -> Bool
  length :: t a -> Int
* elem :: Eq a => a -> t a -> Bool
  maximum :: Ord a => t a -> a
  minimum :: Ord a => t a -> a
  sum :: Num a => t a -> a
  product :: Num a => t a -> a

The issue here is that with just Eq a (barring GADT existentials) we can't do better than a linear search, comparing each element with the desired one. And so, even though Data.Set.Set supports O(log n) search, its elem instance is sadly linear, for lack of an Ord a dictionary.

In !6555 (closed), a work-around is described, where one abandons direct use of elem by introduing a multi-parameter type class, along the lines of:

import qualified Data.Set as Set

class Eq a => HasMember t a where
    member :: a -> t a -> Bool

instance Eq a => HasMember [] a where
    member = elem
[...]
instance Ord a => HasMember Set.Set a where
    member = Set.member

in which instances can specify any additional requisite constraints on the element type, because it appears in the class head along with the structure type.

A fair criticism of the documentation is that the user should reasonably be able to find this class somewhere, rather than being told to how to implement it. That is, it should be in some existing module in base, and packages like containers can then specify appropriate instances.

For now, I think it still makes sense to document that status quo, imperfect as it may be. That said, elem would ideally not have been a Foldable method, but should have been in a separate class, that could support element-type-specific constraints.

Proposal

Consider introducing a new class in base that supports a performant elem-like operation across various container types, taking advantage of any available speedups that the structure in question might support.

Or do nothing??? [ And leave it to users who want a polymorphic member function to implement any additional requisite type class and instances. ]

Or something else?

Cc: @rae , @Kleidukos , @carter