In a recent "Folding the unfoldable" "gist": https://oleg.fi/gists/posts/2022-01-25-folding-unfoldable.html Oleg describes a way to make unboxed Vectors Foldable: There is another way to make Foldable work, with a data Hack a b where Hack :: U.Vector a -> Hack a a This is a two type-parameter wrapper, but the types are always the same! (I wish that could be a newtype). The Foldable instance is simply: instance U.Unbox a => Foldable (Hack a) where foldr f z (Hack v) = U.foldr f z v foldl' f z (Hack v) = U.foldl' f z v In the associated Reddit thread https://www.reddit.com/r/haskell/comments/sd6gel/comment/hudmsis/?utm_source=share&utm_medium=web2x&context=3 it was observed that a similar approach can be used to give Data.Set a performant `elem` method (code copied below my signature). It is somewhat tempting to consider whether the "Hack" ought to be built-in directly into the real Data.Set: https://www.reddit.com/r/haskell/comments/sd6gel/comment/huil070/?utm_source=share&utm_medium=web2x&context=3 type Set a = SetImpl a a data SetImpl a b where Bin :: {-# UNPACK #-} !Size -> !a -> !(SetImpl a) -> !(SetImpl a) -> SetImpl a a Tip :: SetImpl a a type Size = Int instance Ord a => Foldable (SetImpl a) where ... elem _ Tip = False elem x (Bin _ y l r) = case compare x y of EQ -> True LT -> elem x l GT -> elem x r ... This representation does not seem to carry any obvious runtime overhead, and gives Set a performant `elem` method. The only change from the status quo would be that folds would not be available for empty or singleton sets with non-Ord elements (currently possible with Set). How much of a loss would it be to constrain the element type of empty and singleton sets used in folds? Are there other issue that make the above impractical? -- Viktor. type OSet a = OrdSet a a data OrdSet a b where OSet :: Set.Set a -> OrdSet a a instance Ord a => Foldable (OrdSet a) where fold (OSet xs) = fold xs foldMap f (OSet xs) = foldMap f xs foldMap' f (OSet xs) = foldMap' f xs foldr f z (OSet xs) = foldr f z xs foldr' f z (OSet xs) = foldr' f z xs foldl f z (OSet xs) = foldl f z xs foldl' f z (OSet xs) = foldl' f z xs foldr1 f (OSet xs) = foldr1 f xs foldl1 f (OSet xs) = foldl1 f xs toList (OSet xs) = toList xs null (OSet xs) = null xs length (OSet xs) = length xs -- The point of the exercise is `elem` elem e (OSet xs) = Set.member e xs maximum (OSet xs) = maximum xs minimum (OSet xs) = minimum xs sum (OSet xs) = sum xs product (OSet xs) = product xs instance Eq a => Eq (OSet a) where (OSet xs) == (OSet ys) = xs == ys instance (Eq a, Ord a) => Ord (OSet a) where compare (OSet xs) (OSet ys) = compare xs ys empty :: Ord a => OSet a empty = OSet Set.empty singleton :: Ord a => a -> OSet a singleton = OSet . Set.singleton fromList :: Ord a => [a] -> OSet a fromList = OSet . Set.fromList (\\) :: Ord a => OSet a -> OSet a -> OSet a (OSet xs) \\ (OSet ys) = OSet (xs Set.\\ ys) alterF :: (Ord a, Functor f) => (Bool -> f Bool) -> a -> OSet a -> f (OSet a) alterF f x (OSet xs) = fmap OSet $ Set.alterF f x xs ...