CODEWITHSUNDEEP
haskellfunctor
lux_piromani
lux_piromani

Reputation: 21

Haskell: data definition and Functor class

i was trying to define the data type Set but i have problems when i try to instantiate the functor class.

This is my code:

data Set a where
    Empty :: Eq a => Set a
    Add   :: Eq a => a -> Set a -> Set a

instance Functor Set where
    fmap = setMap

setMap :: (Eq a, Eq b) => (a->b) -> Set a -> Set b 
setMap f Empty = Empty
setMap f (Add x set) = Add (f x) $ setMap f set

And this is what the compiler says:

    No instance for (Eq a) arising from a use of ‘setMap’
      Possible fix:
        add (Eq a) to the context of
          the type signature for:
            fmap :: (a -> b) -> Set a -> Set b

Why isn't the constraint in the setMap definition enough? Or, if it is, why is it wrong?

Upvotes: 1

Views: 121

Answers (1)

chepner
chepner

Reputation: 530922

A functor is a pair of functions: a type constructor f that maps one type to another, and a function fmap that maps functions of type a -> b to functions of type f a -> f b. There are no restrictions on what a and b are; both f and fmap need to work for all types.

Set qualifies as the type constructor; given any type a, it returns a new type Set a.

setMap, however, does not work with any two types a and b; it only works with types Eq a => a and Eq b => b.

So, the pair Set/setMap is almost, but not quite, a functor from Hask to Hask (or an endofunctor on Hask), which is what the Functor type class represents. (Hask is the somewhat-controversial category defined as the class of all Haskell types and the functions defined on those types.)

However, one could define a subcategory of Hask called HaskEq, whose objects would be all the Haskell types with an Eq instance. Then Set/setMap would be a endofunctor on HaskEq, since setMap would be valid for any type in HaskEq. There's no easy way to represent HaskEq in Haskell, although Hask is trivial, as shown in Control.Category:

class Category a where
    id :: cat a a
    (.) :: cat b c -> cat a b -> cat a c

-- Hask
instance Category (->) where
    id = GHC.Base.id
    (.) = (GHC.Base..)

But you could define your own type class to represent such endofunctors:

class EqFunctor f where
    eqfmap :: (Eq a, Eq b) => (a -> b) -> f a -> f b

instance EqFunctor Set where
    eqfmap = setMap

Upvotes: 3

Related Questions