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?

Lewendal

Data.IntSet may not be Foldable, but it does provide foldl and foldr implementations. There's also a member function which performs your typical find operation. If you wanted to implement your own find function, there are LookupLE, LookupGT etc functions which would let you perform a binary search. Workaround though. – Otalgia

class Foldable applies to * -> * kinds, and IntSet is a * kind. – Devilfish

@Devilfish you should post that as the answer. Relevant: IntSet is an instance of MonoFoldable. – Lop

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

Marashio

Element should probably be an associated type family. :) – Medeah

@Medeah is there any reason why associated type family better? It's not obvious to me when to choose such option... – Marashio

Thank you for you answer. Can you add how to implement find :: (a -> Bool) -> IntSet -> Maybe a ? – Lewendal

@Marashio Associating the type family gives you a warning when you declare an instance of ProperFoldable without also the type family instance. Otherwise, you are much more likely to end up with stuck type family applications. – Medeah

@Isund I've updated answer with find implementation. – Marashio

To make associating the type pay, add a default definition. type Element t :: a; type Element (f a) = a. Personally, I prefer to make the element type the first class parameter as well, with an equality constraint. – Crinkle

I have to delete my previous comment saying everything is clear. I understand now that a datatype must have kind * -> * to be foldable and that there exists a way to make IntSet foldable with MonoFoldable. What I don't understand is why you can't have a function that efficiently searches for the first Int in an IntSet that satisfies some predicate. In a procedural language, It would make no difference if the container was polymorphic or not. Sorry if this is a stupid question, I'm new to haskell. – Lewendal

@Isund What your predicate exactly does? If you want to find number equals to some other number then there is and efficient way. But what if you want to find any prime number of just even number? You have function of type Int -> Bool and you don't know anything about it inside find function. All you have is list of sorted Ints. For example, I don't know how to implement find even efficiently (faster than O(n)) for sorted list of integers. – Marashio

The function can have linear complexity, I'm not saying anything about the predicate. But your proposed version of find is first converting the set into a list so the complexity should be 2n instead of n worst-case If I'm not mistaken. – Lewendal

@Isund The complexity would be 2n if first list was stored as an intermediate value and only then traversal of find function happen. But Haskell is lazy language. You can think of IS.elems as of lazy iterator which produces values of IntSet on demand and find function calling this iterator while necessary. So in practice there would be no 2n. Always lower. – Marashio