<div dir="ltr"><div><div>Don't be led astray by leaky analogies. A Functor is not a container. <b style="font-size:small">Some</b><span style="font-size:small"> Functor instances are</span><font size="2"><b> like</b> containers. When this analogy stops working, discard it and think about the problem directly. Like any other typeclass, <font face="monospace">Functor</font> is just a collection of methods and laws[1]; its instances are just types which have law abiding implementations of the methods. </font><span style="line-height:1.5">Knowing the type of </span><font face="monospace">fmap</font><span style="line-height:1.5"> and its laws, we know what it means for </span><font face="monospace">((->) r)</font><span style="line-height:1.5"> to be an instance: it means that we can define</span></div></div><div><br></div><div><font face="monospace"> fmap :: (a -> b) -> f a -> f b</font></div><div><br></div><div>for <font face="monospace">f = ((->) r)</font> and prove that it satisfies the laws.<br><div><br></div><div>Substituting for <font face="monospace">f</font>, we have:</div></div><div><br></div><div><font face="monospace"> fmap :: (a -> b) -> (r -> a) -> (r -> b)</font></div><div><br></div><div>By alpha equivalence, we can rename this to</div><div><br></div><div><font face="monospace"> fmap :: (b -> c) -> (a -> b) -> a -> c</font></div><div><br></div><div>and immediately we find a candidate implementation in function composition, <font face="monospace">(.) :: (b -> c) -> (a -> b) -> a -> c</font>:</div><div><br></div><div><font face="monospace"> fmap f g = f . g</font></div><div><br></div><div>Now we must prove that this implementation is law abiding. I'll show a proof for the first law, <font face="monospace">fmap id = id</font>, with assistance from a few definitions:</div><div><br></div><div><font face="monospace">1) f . g = \x -> f (g x)</font></div><div><font face="monospace">2) id x = x</font></div><div><font face="monospace">3) \x -> f x = f</font></div><div><font face="monospace"><br></font></div><div><font face="monospace"> fmap id f</font></div><div><font face="monospace"><span style="line-height:1.5">= id . f {- definition of fmap -}</span><br></font></div><div><span style="line-height:1.5"><font face="monospace">= \x -> id (f x) {- by (1) -}</font></span></div><div><span style="line-height:1.5"><font face="monospace">= \x -> f x {- by (2) -}</font></span></div><div><span style="line-height:1.5"><font face="monospace">= f {- by (3) -}</font></span></div><div><span style="line-height:1.5"><font face="monospace">= id f {- by (2) -}</font></span></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">Thus we have <font face="monospace">fmap id f = id f </font>and (by eta reduction) <font face="monospace">fmap id = id. </font></span><span style="line-height:1.5">Try to prove the second law for yourself! Once you've proven it, you know that </span><font face="monospace">((->) r)</font><span style="line-height:1.5"> is an instance of </span><font face="monospace">Functor</font><span style="line-height:1.5"> where </span><font face="monospace">fmap = (.)</font><span style="line-height:1.5">[2]. </span><span style="line-height:1.5">If you do the same for </span><font face="monospace">Applicative</font><span style="line-height:1.5"> and </span><font face="monospace">Monad</font><span style="line-height:1.5"> then you will know exactly how </span><font face="monospace">((->) r)</font><span style="line-height:1.5"> is a </span><font face="monospace">Functor</font><span style="line-height:1.5">, an </span><font face="monospace">Applicative</font><span style="line-height:1.5">, and a </span><font face="monospace">Monad</font><span style="line-height:1.5">.</span></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">Then you can experiment by applying the typeclass methods to functions to see what the practical value of these definitions is. For example. the <font face="monospace">Applicative</font> instance lets you plumb a shared argument to a number of functions. Here's a contrived example:</span></div><div><span style="line-height:1.5"><br></span></div><div><font face="monospace">> (++) <$> map toUpper <*> reverse $ "Hello"</font><br></div><div><font face="monospace">"HELLOolleH"</font></div><div><br></div><div>-R</div><div><br></div><div>[1] The laws are not really a part of the typeclass proper (i.e., the compiler doesn't know anything about them), but developers need to ensure that their instances are law abiding so that they behave as expected.</div><div>[2]: Actually, it turns out that one only needs to prove the first law for <font face="monospace">fmap</font> because the second law is implied by the first, but that's a topic for another day!</div></div><br><div class="gmail_quote"><div dir="ltr">On Sat, Jun 4, 2016 at 5:11 PM Gesh <<a href="mailto:gesh@gesh.uni.cx">gesh@gesh.uni.cx</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 2016-06-04 19:56, Daniel Bergey wrote:<br>
> I think "a functor is a container" is not so helpful. It works OK for<br>
> Maybe and List, but it doesn't seem helpful in understanding Either,<br>
> Reader, Writer, State, Continuation, promises.<br>
This is correct. However, a large class of types form what are called<br>
"Representable Functors".<br>
These include Lists, Trees, ((->) r), etc.<br>
<br>
A representable functor is any type f with an isomorphism `(f a ~ r -><br>
a)` for some r.<br>
For example, `Stream a ~ Natural -> a` under the isomorphism:<br>
> toFunction xs = \i -> xs !! i<br>
> toList f = fromList $ map f [0..]<br>
> I *think* it's the case that for (r ->), there isn't anything we can do<br>
> with the Monad instance that we can't do with Applicative. If someone<br>
> can confirm or refute that, I'd appreciate it. That's of course not<br>
> true in general for other monads.<br>
Indeed, for any representable functor, this all follows from the fact<br>
that we can write a lawful<br>
join from Reader's <*>. Letting `join m = flip ($) <*> m`, we have:<br>
> (join . pure) x = \r -> ($ r) (const x r) = \r -> x $ r = x<br>
> (join . fmap pure) x = \r -> ($ r) ((pure . x) r) = \r -> (const (x<br>
r)) r = \r -> x r = x<br>
> (join . fmap join) x = \r -> ($ r) ((join . x) r) = \r -> join (x r)<br>
r = \r -> (\s -> ($s) (x r s)) r<br>
> = \r -> x r r r = \r -> ($r) (\s -> x s s) r = join (\s -> ($s) (x<br>
s)) = (join . join) x<br>
<br>
Hence, given the applicative instance for Reader, we obtain the Monad<br>
instance for free.<br>
Therefore, working under the isomorphism, we have the same for any<br>
representable functor.<br>
<br>
In particular, this gives that Stream is a Monad, where return gives the<br>
constant stream and<br>
join takes the diagonal of a stream of streams.<br>
<br>
Again, as noted, this is more or less the only way in which the<br>
"Functors/Applicatives/Monads are nice/nicer/nicest containers" analogy<br>
works.<br>
There are more things in heaven and earth than are described in that<br>
analogy, but it's a start.<br>
<br>
Hope this helps, and that it lacks errors/misleading material,<br>
Gesh<br>
P.S. Code for working with representable functors can be found in<br>
representable-functors.<br>
Code for working with Streams can be found in streams. Both are on Hackage.<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote></div>