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