Is there a name for this subset of bifunctors?

user_2387370 0
Viewed 241

Bifunctors have a map function with this signature:

bimap :: (a -> b) -> (c -> d) -> p a c -> p b d

You could also have a map like this:

othermap :: ((a, c) -> (b, d)) -> p a c -> p b d

Types with this function are a strict subset of bifunctors (you can always define bimap using othermap but not vice versa). Is there a name for the second signature?

Follow-up: what about this intermediate function?

halfothermap :: ((a, c) -> b) -> (c -> d) -> p a c -> p b d
bifunctor functor functional-programming haskell types
2 Answers

A type which is a Bifunctor need not have the same number of a values as b values. Consider, for example,

data TwoLists a b = TwoLists [a] [b]

It is easy to implement bimap, but othermap is a real problem, especially if one of the lists is empty.

othermap f (TwoLists [] (b:bs)) = TwoLists [] _

What can you do here? You need to call f to convert all the bs to a list of type [d], but you can only call that function if you have an a in hand.

Perhaps even worse is a type which doesn't really ever have b values at all:

data TaggedFunction k a b = TaggedFunction a (k -> b)
instance Bifunctor (TaggedFunction k) where
  bimap f g (TaggedFunction a b) = TaggedFunction (f a) (g . b)

How can you implement othermap for this type? You could update the function, because you have an a in hand and will have a b by the time you need a d. But there's no way for you to replace the a with a c, because you can't get hold of a b to call othermap's function with.

So you can't put this function in Bifunctor. Perhaps you're asking, why not put this in a new class? I think leftroundabout is right that the class is too constraining to be useful. othermap can be defined only when you have the same number of as and bs in your structure, i.e. when your structure is some functor f wrapped around a tuple of type (a, b). For example, instead of TwoLists we could have defined

newtype PairList a b = PairList [(a, b)]

and that can have an othermap definition. But it would just be

othermap f (PairList vs) = PairList (fmap f vs)

Likewise instead of TaggedFunction we could have defined

newtype MultiFunction k a b = MultiFunction (k -> (a, b))

but the othermap definition is again just a wrapped call to fmap:

othermap f (MultiFunction g) = MultiFunction (fmap f g)

So perhaps the best way to imagine defining this abstraction would be as, not a typeclass function, but an ordinary function that operates over a type that captures this composition:

newtype TupleFunctor f a b = TupleFunctor (f (a, b))

othermap :: Functor f => ((a, b) -> (c, d)) 
                      -> TupleFunctor f a b -> TupleFunctor f c d
othermap f (TupleFunctor x) = TupleFunctor (fmap f x)
user_6254030

(Expanding on a comment by @glennsl...)

The type p a c "contains" both a and c.

But a function of type (a, c) -> (b, d) requires values of type a and c to be called, and a value of type p a c doesn't necessarily have both.

othermap @Either :: ((a, c) -> (b, d)) -> Either a c -> Either b d
othermap f (Left x) = ?
othermap f (Right y) = ?

There's no way for othermap to produce values of type b or d, because it can't call f in either case.

The type of the first argument implies a bifunctor that is isomorphic to (,), which is not true of all possible bifuntors. othermap is, in fact, strictly more specific than bimap. (There seems to be a contravariant relationship here that I won't try to make precise.)

user_11268410
Related