haskellfunctorcategory-abstractions

Why this structure-preserving "fmap" cannot be acepted in this Functor's class instance?

The below defined function mapRightR change only the map's set contents, not the keys and produce a valid Relation type.

Is it really impossible use this high-level function to define the Functor Relation instance, or is my implementation wrong.

{-# LANGUAGE GADTs #-}

import Data.Map as M
import Data.Set as S

data Relation a b where
    R :: (Ord a, Ord b) => Map a (Set b) -> Relation a b

instance Functor Relation where
    fmap f r = mapRightR f r

mapRightR :: Ord b1 => (b2 -> b1) -> Relation a b2 -> Relation a b1
mapRightR f (R r) = R $ M.map (S.map f) r

Thanks, chepner.

I tried another definition of Relation, using List instead of Set and it work!

data Relation a b where
    R :: (Ord a) => Map a [b] -> Relation a b

instance Functor (Relation a) where
    fmap f r = mapRightR f r

mapRightR :: (b2 -> b1) -> Relation a b2 -> Relation a b1
mapRightR f (R r) = R $ M.map (L.map f) r
Solution

  • mapRightR is constrained, it will not work for any type b as fmap requires:

    -- Specialized for f ~ Relation c
fmap ::               (a -> b) -> Relation c a -> Relation c b

    but

    mapRightR :: Ord b => (a -> b) -> Relation c a -> Relation c b

    In more categorical terms, Relation c is not an endofunctor that maps Hask to Hask (which is what the Functor typeclass represents), but rather a functor that maps a subcategory of Hask consisting only of types with Ord instances to Hask. (I think I characterized this correctly; corrections welcome.)