0
$\begingroup$

"Composition of Composition" (i.e., (.) . (.)) in Haskell), has type (a -> b) -> (c -> d -> a) -> c -> d -> b. Apparently, this is an instance of fmap, i.e. a functor between two categories.

The question is: what is the domain and the codomain of this functor? How do we interpret this functor in terms of functional programming?

$\endgroup$
4
  • $\begingroup$ No, fmap can not have that type. fmap . fmap can, since fmap = (.) for the functor X -> - (for any X). In your case, the two functors are c -> - and d -> -. (For total obfuscation, fmap . fmap can be also be written as fmap fmap fmap) $\endgroup$
    – chi
    Commented Nov 30, 2018 at 17:22
  • $\begingroup$ Anyway, I think that this question is a bit too much Haskell-specific to be here. On StackOverflow we routinely handle Haskell questions asking for the underlying categorical ideas (and how faithfully, or not, they appear in Haskell). $\endgroup$
    – chi
    Commented Nov 30, 2018 at 17:25
  • $\begingroup$ @chi It is certainly not true that this question is specific to Haskell - we get categories in any pure subset of typed functional programming languages. Writing this in SML for instance does not magically change the categories involved. $\endgroup$
    – xuq01
    Commented Nov 30, 2018 at 21:12
  • $\begingroup$ @xuq01 Actually, it likely does change the categories involved (at least to the extent that it is meaningful to talk about categories). $\endgroup$ Commented Dec 1, 2018 at 17:29

1 Answer 1

1
$\begingroup$

Consider

(.) :: (a -> b) -> (d -> a) -> d -> b

is the fmap for functor $F_d\colon \mathfrak{C} \rightarrow d/\mathfrak{C}$ from category of types $\mathfrak{C}$ to its coslice category $d/\mathfrak{C}$ on object $d$. Similarly,

(.) :: ((d -> a) -> d -> b) -> (c -> d -> a) -> c -> d -> b

is considered the fmap for functor $G_c\colon d/\mathfrak{C} \rightarrow c/\big(d/\mathfrak{C}\big)$.

These two functor can be composed to get $G_c \circ F_d\colon \mathfrak{C} \rightarrow c/\big(d/\mathfrak{C}\big)$. Like all compositions of two functors, the fmap of the composed functor is the composition of fmap its two functor operands. In this case, the fmap of $G_c \circ F_d$ is

(.) . (.) :: (a -> b) -> (c -> d -> a) -> c -> d -> b

as in the opening question.

$\endgroup$
1
  • $\begingroup$ I realise the answer is only half right. The fact that category of types is closed needs to be used to make sense. Please correct it if you can. $\endgroup$ Commented Sep 3, 2019 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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