## 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, 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