I hate the environment functor
Here we have the wellknown fmap function:
fmap :: Functor f => (a > b) > f a > f b
It takes a single function and a (collection of input values /
decorated input value / something something input value) and produces
a (collection of output values / decorated output value / something
something output value).
Yow, that's not going to work. Is there any good terminology for a
value of type f a when f is an arbitrary functor? A while back I
discussed a similar
problem and suggested
the term “mote” for a value in a monadic type. I will try calling an
f t value a “t parcel and see how that works. So
[t] , Maybe t , and IO t are all examples of t parcels, in
various functors.
Starting over then. Here we have the wellknown fmap function:
fmap :: Functor f => (a > b) > f a > f b
It takes a single function, and an a parcel, and produces a b
parcel, by applying the function independently to the a values in
the parcel.
Here is a sort of reversed version of fmap that I call pamf :
pamf :: Functor f => f (a > b) > a > f b
It takes a parcel of functions, and a single input and produces a
parcel of outputs, by applying each function in the parcel
independently to the single a value. It can be defined in terms of
fmap :
pamf fs a = fmap ($ a) fs
So far so good. Now I ask you to predict the type of
pamf fmap
Certainly it should start out with
pamf fmap :: (Functor f, Functor g) => ...
because the pamf and the fmap might be operating in two different
functors, right? Indeed, if I compose the functions the other way
around, fmap pamf , the type does begin this way; it is:
(Functor f, Functor g) => f (g (a > b)) > f (a > g b)
The f here is the functor in which fmap operates, and the g is
the functor in which pamf is operating. In general fmap takes an
arbitrary function
a > b
and lifts it to a new function that operates in the f functor:
f a > f b
Here it has taken pamf , which is a function
g (a > b) > (a > g b)
and lifted it to a new function that operates in the f functor:
f (g (a > b)) > f (a > g b)
This is complicated but straightforward. Okay, that was fmap pamf .
What about pamf fmap though? The computed type is
pamf fmap :: Functor f => f a > (a > b) > f b
and when I saw this I said “What. Where did g go? What happened to
g ?”
Then I paused and for a while and said “… I bet it's that goddamn
environment thing again.” Yep, that's what it was. It's the
environment functor, always turning up where I don't want it and
least expect it, like that one guy we all went to college with. The
environment functor, by the way, is yet another one of those things
that Haskell ought to have a standard name for, but doesn't. The
phrase “the reader monad” is fairly common, but here I only want the
functor part of the monad. And people variously say “reader monad”,
“environment monad”, and “evaluation monad” to mean the same thing.
In this article, it will be the environment functor.
Here's what happened. Here are fmap and pamf again:
fmap :: Functor f => (p > q) > f p > f q
pamf :: Functor g => g (a > b) > a > g b
The first argument to pamf should be a parcel in the g functor.
But fmap is not a parcel, so pamf fmap will be a type error,
right? Wrong! If you are committed enough, there is a way to
construe any function as a parcel. A function p > q is a q
parcel in the environment functor. Say that g denotes an
environment functor. In this functor, a parcel of type g t is a
function which consults an “environment” of type e and yields a
result of type t . That is, $$g t \equiv e \to t.$$
When operating in the environment functor, fmap has the type (a >
b) > g a > g b , which is shorthand for (a > b) > (e > a) > (e
> b) . This instance of fmap is defined this way:
fmap f x = \e > f (x e)
or shorter and more mysteriously
fmap = (.)
which follows by ηreduction, something Haskell enthusiasts never seem
to get enough of.
In fmap f x , the x isn't the actual value to give to f ; instead
it's a parcel, as it always is with fmap . In the context of the
environment functor, x is a function that consults the environment
e and returns an a . The result of fmap f x is a new parcel: it
uses x to consult the supplied environment for a value of type a ,
which it then feeds to f to get the required value of type b .
In the application pamf fmap , the left side pamf wants fmap to
be a parcel. But it's not a parcel, it's a function. So, type error,
right? No! Any function is a parcel if you want it to be, it's a
parcel in the environment functor! And fmap is a function:
fmap :: Functor f => (p > q) > f p > f q
so it can be understood as a parcel in the environment functor, where
the environment e has type p > q . Then pamf is operating in
this environment functor, so $$g t = (p \to q) \to t.$$ A g t parcel
is a function that consults an “environment” of type p > q and
somehow produces a t value. (Haskell folks, who are obsessed with
currying all the things, will write this as the
nearly unreadable g = ((>) (p > q)) .)
We wanted pamf to have this type:
pamf :: Functor g => g (a > b) > a > g b
and since Haskell has decided that g must be the environment functor
with !!g x \equiv (p \to q) \to x!!,
this is an abbreviation for:
pamf :: ((p > q) > (a > b)) > a > ((p > q) > b)
To apply this to fmap , we have to unify the type of pamf 's
argument, which is (p > q) > (a > b) , and the type of fmap ,
which is (p > q) > (f p > f q) . Then !!a\equiv f p!! and !!b
\equiv f q!!, so the result of pamf fmap is
pamf fmap :: Functor f => f p > ((p > q) > f q)
Where did g go? It was specialized to mean the environment functor
((>) (p > q)) , so it's gone.
The funny thing about the type of pamf fmap is that it is exactly
the type of flip fmap , which is fmap with the order of its two
arguments reversed:
(flip fmap) x f ≡ fmap f x
and indeed, by some theorem or other, because the types are identical,
the functions themselves must be identical also! (There are some side
conditions, all of which hold here.) The two functions pamf fmap and
flip fmap are identical. Analogous to the way fmap , restricted
to the environment functor, is identical to (.) , pamf , when
similarly restricted, is exactly
flip . You can even see this from its type:
pamf :: ((p > q) > (a > b)) > a > ((p > q) > b)
Or, cleaning up some superfluous parentheses and inserting some new ones:
pamf :: ((p > q) > a > b) > (a > (p > q) > b)
And putting !!c = p\to q!!:
pamf :: (c > a > b) > (a > c > b)
flip :: ( the same )
Honestly, I would have preferred a type error: “Hey, dummy, fmap has
the wrong type to be an argument to pamf , which wants a functorial
value.” Instead I got “Okay, if you want functions to be a kind of
functor I can do that, also wouldn't it be simpler if the universe was
twodimensional and there were only three kinds of quarks? Here you
go, no need to thank me!” Maybe someone can explain to me why this is
a useful behavior, and then explain why it is so useful that it should
happen automatically and implicitly instead of being triggered
by some lexical marker like:
newtype Environment e a = Environment (e > a)
instance Functor (Environment e) where
fmap f (Environment x) = Environment $ \e > f (x e)
I mean, seriously, suppose you wrote a + b where b was
accidentally a function instead of a number. What if when you did
that, instead of a type error, Haskell would silently shift into some
restricted domain in which it could implicitly interpret b as a
number in some weird way and give you something totally bizarre?
Isn't the whole point of Haskell supposed to be that it doesn't
implicitly convert things that way?
[Other articles in category /prog/haskell]
permanent link
