4
$\begingroup$

I was reading 'Category Theory for Programmers' by Bartosz Milewski and got really confused by the implementation of bimap in Bifunctor typeclass.

class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d 
    bimap g h = first g . second h
    first :: (a -> c) -> f a b -> f c b
    first g = bimap g id
    second :: (b -> d) -> f a b -> f a d
    second = bimap id

This is the definition of the Bifunctor typeclass taken directly from the library Control. If bimap evaluates to first and second, which in turn evaluates to bimap itself, how is this supposed to end? Could you please explain how the evaluation of bimap works? Thank you!

$\endgroup$
4
$\begingroup$

A Haskell type class defines a set of functions (sometimes called methods) that belong to the type class. In most cases, specific instances must supply specific implementations of one or more of these.

An instance can implement all methods, or just enough to make the instance work. If an instance doesn't implement all methods, the default implementations are used.

Type classes are typically documented with the minimal implementation required. This is also true for Bifunctors:

Minimal complete definition

bimap | first, second

This means that an instance must implement either bimap, or both first and second. An instance can also implement all three, but that's not required.

The tuple instance, for example, is implemented using bimap:

instance Bifunctor (,) where
  bimap f g ~(a, b) = (f a, g b)

This means that the first and second implementations are the default implementations you quoted above. They call the instance's bimap implementation.

$\endgroup$
  • $\begingroup$ Thank you! I am new to Haskell and didn't know there's this thing called minimal complete definition, now I understand how it works. $\endgroup$ – Qiu Haohao Dec 20 '19 at 9:54
  • $\begingroup$ After reading this answer, I am aware of the difference between a class and an instance, then the class definition makes sense to me. $\endgroup$ – C.W. Feb 20 '20 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.