Is there a Functor that cannot be a law-abiding Apply?
The "sum" of two functors (Data.Functor.Sum
from transformers
) seems to be an example.
One can easily map over one branch or the other, but how to implement <.>
when the function-in-the-functor and the argument-in-the-functor lie in different branches?
ghci> import Data.Functor.Sum
ghci> import Data.Functor.Identity
ghci> let f = InL (Const ()) :: Sum (Const ()) Identity (Int -> Int)
ghci> let x = InR (Identity 5) :: Sum (Const ()) Identity Int
ghci$ f <.> x = ..... ?
Yes, there are Functor
s 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 i
s and j
s:
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 i
s and j
s
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 Functor
s 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 absurd
ly 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 a
s; 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 Functor
s 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.