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.
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.
Functor in Haskell is a typeclass that provides two methods – fmap and (<$) – for structure-preserving transformations. To implement a Functor instance for a data type, you need to provide a type-specific implementation of fmap – the function we already covered.
String is not a functor, because it has the wrong kind.
Functor is also important in its role as a superclass of Applicative and of Traversable . When working with these more powerful abstractions, it's often very useful to reach for the fmap method. Show activity on this post. For example, it's possible to derive the function lift in a way that works for any functor.
Another simple example of a functor is the Maybe type. This object can contain a value of a particular type as Just , or it is Nothing (like a null value).
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.
... 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.
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 <.>
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 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
... 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.
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 = ..... ?
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With