The `elem` method of `Foldable` is a poor abstraction for structures with faster than linear search
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 (
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
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.
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