Search code examples
haskellfunctor

Is there a Functor that cannot be a law-abiding Apply?

A recent question asked generally about boundaries between various Haskell classes. I came up with Handler as an example of a valid Functor with no sensible instance of Apply**, where

class Functor f => Apply f where
  (<.>) :: f (a -> b) -> f a -> f b
  -- optional bits omitted.

However, I've not yet been able to find an example of a valid Functor that cannot be made a valid (if senseless) instance of Apply. The fact that Apply has had (see update) but a single law,

(.) <$> u <.> v <.> w = u <.> (v <.> w)

seems to make this rather tricky.

pigworker (Conor McBride) previously gave an example of a Functor that is not Applicative, but he relied on pure to do so, and that's not available in Apply.

** Then later I realized there actually might be a sensible (although slightly strange) Apply instance for Handler, that conceptually collects simultaneous exceptions.

Update

Edward Kmett has now accepted two additional laws I proposed for Apply (to validate optimizations I made to the Apply (Coyoneda f) instance):

x <.> (f <$> y) = (. f) <$> x <.> y
f <$> (x <.> y) = (f .) <$> x <.> y

It would be interesting to see whether these additions change the answer to this question.

Solution

  • Yes, there are Functors with no Apply instance. Consider the sum of two functions (which are exponents in algebraic data types):

    data EitherExp i j a
    = ToTheI (i -> a)
    | ToTheJ (j -> a)

    There's a Functor instance for all is and js:

    instance Functor (EitherExp i j) where
    fmap f (ToTheI g) = ToTheI (f . g)
    fmap f (ToTheJ g) = ToTheJ (f . g)

    but there's no Apply instance for all is and js

    instance Apply (EitherExp i j) where
    ...
    ToTheI f <.> ToTheJ x = ____

    There's no way to fill in the blank ____ with an i -> b or a j -> b when all you have is f :: i -> a -> b and x :: j -> a. To do so we'd have to know something about i and j, but there's no way to look inside every type i or j in Haskell. Intuition rejects this answer; if you know anything about i or j, like that they are inhabited by a single value, then you can write an Apply instance for EitherExp

    class Inhabited a where
    something :: a

instance (Inhabited i, Inhabited j) => Apply (EitherExp i j) where
    ...
    ToTheI f <.> ToTheJ x = ToTheI (const ((f something) (x something)))

    But we don't know that every i and every j is Inhabited. The Void type isn't inhabited by anything. We don't even have a way to know that every type is either Inhabited or Void.

    Our intuition is actually very good; when we can inspect how types are constructed, for algebraic data types there are no Functors that don't have Apply instances. What follow are two answers that might be more pleasing to our intuition.

    No ...

    ... for algebraic data types. There are 3 possibilities. The structure is void, the structure can be empty, or the structure can't be empty. If the structure is void then it's absurdly an Apply. If it can be empty, chose any empty instance and return it constantly for any apply. If it can't be empty then it's a sum of structures that each can't be empty, a law-abiding apply can be made by applying one of the values† from the first to one of the values from the second and returning it in some constant structure.

    The apply law is very lax. Apply doesn't need to make any sense. It doesn't need to be "zip-y". It doesn't need to be fmap when combined with things suspiciously like pure from Applicative; there's no notion of pure with which to write a law requiring it to make sense.

    When the structure can be empty

    Chose any empty instance and return it constantly for any apply

    u <.> v = empty

    Proof

      (.) <$> u  <.> v  <.> w = u <.> (v <.> w)
(((.) <$> u) <.> v) <.> w = u <.> (v <.> w) -- by infixl4 <$>, infixl4 <.>
(_                ) <.> w = u <.> (_      ) -- by substitution
                    empty = empty           -- by definition of <.>

    When the structure can't be empty

    If the structure f can't be empty, there exists a function extract :: forall a. f a -> a. Choose another function c :: forall a. a -> f a that always constructs the same non-empty structure populated with the argument everywhere and define:

    u <.> v = c (extract u $ extract v)

    With the free theorems

    extract (f <$> u) = f (extract u)
extract . c = id

    Proof

      (.) <$> u  <.> v  <.> w = u <.> (v <.> w)
(((.) <$> u) <.> v) <.> w = u <.> (v <.> w) -- by infixl4 <$>, infixl4 <.>
(c (extract ((.) <$> u) $ extract v)) <.> w = u <.> (v <.> w) -- by definition
(c ((.) (extract u)     $ extract v)) <.> w = u <.> (v <.> w) -- by free theorem 
c (extract (c ((.) (extract u) $ extract v)) $ extract w) = u <.> (v <.> w) -- by definition
c (           ((.) (extract u) $ extract v)  $ extract w) = u <.> (v <.> w) -- by extract . c = id
c (((.) (extract u) $ extract v) $ extract w) = u <.> c (extract v $ extract w) -- by definition
c (((.) (extract u) $ extract v) $ extract w) = c (extract u $ extract (c (extract v $ extract w))) -- by definition
c (((.) (extract u) $ extract v) $ extract w) = c (extract u $            (extract v $ extract w) ) -- by extract . c = id
let u' = extract u
    v' = extract v
    w' = extract w
c (((.) u' $ v') $ w') = c (u' $ (v' $ w'))
c ((u' . v') $ w') = c (u' $ (v' $ w')) -- by definition of partial application of operators
c (u' $ (v' $ w')) = c (u' $ (v' $ w')) -- by definition of (.)

    A little more deserves to be said about defining extract for the exponential types, functions. For a function i -> a there are two possibilities. Either i is inhabited or it isn't. If it is inhabited, choose some inhabitant i† and define

    extract f = f i

    If i is uninhabited (it's void) then i -> a is the unit type with the single value absurd. Void -> a is just another elaborate empty type that doesn't hold any as; treat it as a structure that can be empty.

    When the structure is void

    When the structure is void there are no ways to construct it. We can write a single function from every possible construction (there are none to pass to it) to any other type.

    absurd :: Void -> a
absurd x = case x of {}

    Void structures can be Functors with fmap f = absurd. In the same way they can have an Apply instance with 

    (<.>) = absurd

    We can trivially prove that for all u, v, and w

    (.) <$> u  <.> v  <.> w = u <.> (v <.> w)

    There are no u, v, or w and the claim is vacuously true.

    †With some caveats about accepting the axiom of choice to choose an index a for the exponential type a -> b

    Yes ...

    ... for Haskell. Imagine there's another base Monad other than IO, let's call it OI. Then Sum IO OI is a Functor but can never be an Apply.

    ... for the real world. If you have a machine to which you can send functions (or arrows in a category other than Hask), but cannot combine two of the machines together or extract their running state, then they are a Functor with no Apply.