Foldable IntSet

Question

For me, an integer set seems to be a foldable data structure. Why is Data.IntSet not an instance of Foldable?

My actual intention is to use find on an IntSet. How can I implement find for Data.IntSet?

Answer 1

IntSet can't be Foldable from base package because it doesn't have kind * -> *.

ghci> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
ghci> :k Foldable
Foldable :: (* -> *) -> Constraint
ghci> import Data.IntSet (IntSet)
ghci> :k IntSet
IntSet :: *

In simple words, to be instance of Foldable from base you data type should be parametrized by some type variable. If you want to use some operation on IntSet you should use some function from Data.IntSet module where all specialized versions implemented.

But I want to add that there exist version of Foldable which IntSet can instantiate (and we actually did this in our library and this was done earlier with MonoFoldable). You just need to implement your abstractions properly:

{-# LANGUAGE TypeFamilies #-}

type family Element t
type instance Element (f a)  = a
type instance Element Text   = Char
type instance Element IntSet = Int

class ProperFoldable t where
    foldr :: (Element t -> b -> b) -> b -> t -> b

UPDATE (adding find by request):

You can't implement find :: (a -> Bool) -> IntSet -> Maybe a because of a type variable. Can you answer question «What is a?»? IntSet is not polymorphic container. It contains only Ints. So maximum you can implement is find :: (Int -> Bool) -> IntSet -> Maybe Int. And there's no efficient way to implement this function, only by converting IntSet to list like this:

import           Data.Foldable (find)
import           Data.IntSet (IntSet)
import qualified Data.IntSet as IS

intSetFind :: (Int -> Bool) -> IntSet -> Maybe Int
intSetFind predicate = find predicate . IS.elems