7

We can have two types f, g :: * -> * such that they're not monads, but their composition is. For example for an arbitrary fixed s:

f a := s -> a
g a := (s, a)

g a isn't a monad (unless we restrict s to a monoid), but f (g a) is the state monad s -> (s, a). (Unlike functors and applicative functors, even if both f and g were monads, their composition might not be.)

Is there a similar example for functors or applicative functors? That is that the composition of f and g is a a functor (or an applicative functor), even though

  1. one of f and g isn't an (applicative) functor and the other is, or
  2. neither of them is an (applicative) functor,
Community
  • 1
  • 1
Petr
  • 62,528
  • 13
  • 153
  • 317
  • 2
    The `ContT` transformer makes `Functor`s and `Applicative`s without requiring that the transformed structure is a `Functor`, but isn't built by composition. http://hackage.haskell.org/package/transformers-0.4.1.0/docs/Control-Monad-Trans-Cont.html#t:ContT Similarly, the free applicative `Ap` adds `Applicative` behavior to any `Functor`, without requiring that it be `Applicative`, but again isn't built by composition. http://hackage.haskell.org/package/free-4.9/docs/Control-Applicative-Free.html#t:Ap – Cirdec Sep 21 '14 at 17:23
  • perhaps not an answer but whenever `F` and `G` are adjoint you get a monad in the composition. – Philip JF Sep 22 '14 at 09:54

2 Answers2

8

This is not a (covariant) functor

f x = x -> r

but f . f is the "continuation" functor (also a monad):

f (f x) = (x -> r) -> r

This is probably not the best example because f is a contravariant functor.

chi
  • 111,837
  • 3
  • 133
  • 218
  • I'm mainly interested in covariant functors, so I don't mind if `f` is contravariant, the example is fine. – Petr Sep 21 '14 at 12:56
  • 1
    Do you think it'd be possible to find an example where `f` is a functor but `g` isn't (and `f . g` is)? – Petr Sep 21 '14 at 13:00
7

Let g :: *->*. Then Const A . g is a functor for any A, in fact isomorphic to Const A.

leftaroundabout
  • 117,950
  • 5
  • 174
  • 319