Functions as containers; implications on being a Monad ((->) r)
Everyone agrees ((->) r) is a Functor, an Applicative and a Monad but I've never seen any good writeup going into details of explaining this. So I was trying to brainstorm with my brother and went pretty far into the concept for quite a few hours, but still got stuck when it came to Monads. Before I showcase the question/problem I wanted to share our thinking process. Lets stick with common types like Maybe a, [a], simple function (a -> b) **Everything is a Container** Just 4 => this is a container wrapping some value [1,2,3] => this is a container wrapping bunch of values (+3) => this is a container wrapping domains & ranges (infinite dictionary) **When is a Container a Functor** If we can peek inside a container and apply a simple function (a->b) to each of its values and wrap the result back inside the container, then it becomes a Functor. Let's use (\x -> x+7) as simple function along with above three Containers (\x -> x+7) <$> Just 4 => Just 11 (\x -> x+7) <$> [1,2,3] => [8,9,10] (\x -> x+7) <$> (+3) => (+10) -- well there is no Show defined but you get the idea **When is a Container an Applicative** The simple function from above is also now wrapped inside a container and we should be able to peek to use it just like functor. Also lets simplify (\x -> x+7) to (+7). Just (+7) <*> Just 4 => Just 11 [(+7)] <*> [1,2,3] => [8,9,10] (\x -> (+7)) <*> (+3) => (+10) -- again no Show defined but works when pass a number -- but (+7) still needs to be wrapped in a Container though **When is a Container a Monad** This time we don't have a simple function (a->b) instead we have a non-simple function (a -> Container). But rest stays almost the same. We have to first peek inside a container and apply non-simple function to each of its values. Since its a non-simple function we need to collect all the returned Containers, unwrap them and wrap them all back in a Container again. (it almost feels like unwrap and wrapping them back is going to complicate things) Also Non-simple function cannot be reused as is for all three Containers like in Functors & Applicatives. Just 4 >>= (\x -> Just (x+7)) => Just 11 [1,2,3] >>= (\x -> [x+7]) => [8,9,10] (+3) >>= (\x -> (+7)) => (+7) Wait a minute ... the last line doesn't look right. Or should I say it doesn't feel right to discard the `x' altogether. OK let's jump to do this: (+3) >>= (\x -> (+x)) => ??? -- apparently this solves for the equation: f(x) = 2x + 3 (is 2x + 3 obvious for anyone??? it took us way longer to derive it) (Does it have anything to do with Monad laws by any chance?) This is where it feels like "Functions as containers" concept starts to breakdown; its not the right analogy for Monads. What does it even mean to unwrap a bunch of functions and wrap them back again? Hope this intrigues some of you as it did to us. Any thoughts and comments greatly appreciated. Thanks, Raja
I think "a functor is a container" is not so helpful. It works OK for
Maybe and List, but it doesn't seem helpful in understanding Either,
Reader, Writer, State, Continuation, promises.
For the instance ((->) r), it's important to keep track of which argument is the
r. I think it helps to write the lambdas explicitly, rather than the
point-free (+3). Keeping the type variables straight is also a reminder
that all these need to work for any types r, a, b, not only when all
three types are Int: (r ~ a ~ b ~ Int).
So we have:
fmap :: (a -> b) -> (r -> a) -> (r -> b)
fmap f g = \r -> f (g r)
fmap (\x -> x + 7) (\r -> r + 3) = \r -> (r + 3) + 7
(<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)
f <*> g = \r -> f r (g r)
Since r, a, b may all be different types, this is the only possible definition.
(\r -> (\x -> x + 7)) <*> (\r -> r + 3) = \r -> (r + 3) + 7
Note that the function on the left of <*> ignores its r parameter, so
this is exactly the same as the fmap example. This follows the law (for
any Applicative) that
fmap f === pure f <*>
For an example that doesn't ignore the r:
(\r -> (\x -> r + x)) <*> (\r -> r + 3) = \r -> r + (r + 3)
Note also that the function on the left takes the argument of type r
first, and the argument of type a second. The second argument to >>=,
on the other hand, takes an a, then an r:
(>>=) :: (r -> a) -> (a -> (r -> b)) -> (r -> b)
f >>= g = \r -> g (f r)
(\r -> r + 3) >>= (\x -> (\r -> r + 7)) = \r -> r + 7
Here the function on the right of >>= ignores its argument, so this
isn't very interesting.
(\r -> r + 3) >>= (\x -> (\r -> r + x)) = \r -> r + (r + 3)
is a bit more interesting. It uses both functions, but it's exactly the
same as the second Applicative example.
I *think* it's the case that for (r ->), there isn't anything we can do
with the Monad instance that we can't do with Applicative. If someone
can confirm or refute that, I'd appreciate it. That's of course not
true in general for other monads.
Hope this helps.
bergey
On 2016-06-04 at 00:40, Raja
Everyone agrees ((->) r) is a Functor, an Applicative and a Monad but I've never seen any good writeup going into details of explaining this.
So I was trying to brainstorm with my brother and went pretty far into the concept for quite a few hours, but still got stuck when it came to Monads.
Before I showcase the question/problem I wanted to share our thinking process.
Lets stick with common types like Maybe a, [a], simple function (a -> b)
**Everything is a Container**
Just 4 => this is a container wrapping some value [1,2,3] => this is a container wrapping bunch of values (+3) => this is a container wrapping domains & ranges (infinite dictionary)
**When is a Container a Functor**
If we can peek inside a container and apply a simple function (a->b) to each of its values and wrap the result back inside the container, then it becomes a Functor.
Let's use (\x -> x+7) as simple function along with above three Containers
(\x -> x+7) <$> Just 4 => Just 11 (\x -> x+7) <$> [1,2,3] => [8,9,10] (\x -> x+7) <$> (+3) => (+10) -- well there is no Show defined but you get the idea
**When is a Container an Applicative**
The simple function from above is also now wrapped inside a container and we should be able to peek to use it just like functor. Also lets simplify (\x -> x+7) to (+7).
Just (+7) <*> Just 4 => Just 11 [(+7)] <*> [1,2,3] => [8,9,10] (\x -> (+7)) <*> (+3) => (+10) -- again no Show defined but works when pass a number -- but (+7) still needs to be wrapped in a Container though
**When is a Container a Monad**
This time we don't have a simple function (a->b) instead we have a non-simple function (a -> Container). But rest stays almost the same.
We have to first peek inside a container and apply non-simple function to each of its values. Since its a non-simple function we need to collect all the returned Containers, unwrap them and wrap them all back in a Container again. (it almost feels like unwrap and wrapping them back is going to complicate things)
Also Non-simple function cannot be reused as is for all three Containers like in Functors & Applicatives.
Just 4 >>= (\x -> Just (x+7)) => Just 11 [1,2,3] >>= (\x -> [x+7]) => [8,9,10] (+3) >>= (\x -> (+7)) => (+7)
Wait a minute ... the last line doesn't look right. Or should I say it doesn't feel right to discard the `x' altogether.
OK let's jump to do this: (+3) >>= (\x -> (+x)) => ??? -- apparently this solves for the equation: f(x) = 2x + 3
(is 2x + 3 obvious for anyone??? it took us way longer to derive it) (Does it have anything to do with Monad laws by any chance?)
This is where it feels like "Functions as containers" concept starts to breakdown; its not the right analogy for Monads.
What does it even mean to unwrap a bunch of functions and wrap them back again?
Hope this intrigues some of you as it did to us. Any thoughts and comments greatly appreciated.
Thanks, Raja
_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
On 2016-06-04 19:56, Daniel Bergey wrote:
I think "a functor is a container" is not so helpful. It works OK for Maybe and List, but it doesn't seem helpful in understanding Either, Reader, Writer, State, Continuation, promises. This is correct. However, a large class of types form what are called "Representable Functors". These include Lists, Trees, ((->) r), etc.
toFunction xs = \i -> xs !! i toList f = fromList $ map f [0..] I *think* it's the case that for (r ->), there isn't anything we can do with the Monad instance that we can't do with Applicative. If someone can confirm or refute that, I'd appreciate it. That's of course not true in general for other monads. Indeed, for any representable functor, this all follows from the fact
A representable functor is any type f with an isomorphism `(f a ~ r -> a)` for some r. For example, `Stream a ~ Natural -> a` under the isomorphism: that we can write a lawful join from Reader's <*>. Letting `join m = flip ($) <*> m`, we have:
(join . pure) x = \r -> ($ r) (const x r) = \r -> x $ r = x (join . fmap pure) x = \r -> ($ r) ((pure . x) r) = \r -> (const (x r)) r = \r -> x r = x (join . fmap join) x = \r -> ($ r) ((join . x) r) = \r -> join (x r) r = \r -> (\s -> ($s) (x r s)) r = \r -> x r r r = \r -> ($r) (\s -> x s s) r = join (\s -> ($s) (x s)) = (join . join) x
Hence, given the applicative instance for Reader, we obtain the Monad instance for free. Therefore, working under the isomorphism, we have the same for any representable functor. In particular, this gives that Stream is a Monad, where return gives the constant stream and join takes the diagonal of a stream of streams. Again, as noted, this is more or less the only way in which the "Functors/Applicatives/Monads are nice/nicer/nicest containers" analogy works. There are more things in heaven and earth than are described in that analogy, but it's a start. Hope this helps, and that it lacks errors/misleading material, Gesh P.S. Code for working with representable functors can be found in representable-functors. Code for working with Streams can be found in streams. Both are on Hackage.
Don't be led astray by leaky analogies. A Functor is not a container. *Some* Functor instances are* like* containers. When this analogy stops working, discard it and think about the problem directly. Like any other typeclass, Functor is just a collection of methods and laws[1]; its instances are just types which have law abiding implementations of the methods. Knowing the type of fmap and its laws, we know what it means for ((->) r) to be an instance: it means that we can define fmap :: (a -> b) -> f a -> f b for f = ((->) r) and prove that it satisfies the laws. Substituting for f, we have: fmap :: (a -> b) -> (r -> a) -> (r -> b) By alpha equivalence, we can rename this to fmap :: (b -> c) -> (a -> b) -> a -> c and immediately we find a candidate implementation in function composition, (.) :: (b -> c) -> (a -> b) -> a -> c: fmap f g = f . g Now we must prove that this implementation is law abiding. I'll show a proof for the first law, fmap id = id, with assistance from a few definitions: 1) f . g = \x -> f (g x) 2) id x = x 3) \x -> f x = f fmap id f = id . f {- definition of fmap -} = \x -> id (f x) {- by (1) -} = \x -> f x {- by (2) -} = f {- by (3) -} = id f {- by (2) -} Thus we have fmap id f = id f and (by eta reduction) fmap id = id. Try to prove the second law for yourself! Once you've proven it, you know that ((->) r) is an instance of Functor where fmap = (.)[2]. If you do the same for Applicative and Monad then you will know exactly how ((->) r) is a Functor, an Applicative, and a Monad. Then you can experiment by applying the typeclass methods to functions to see what the practical value of these definitions is. For example. the Applicative instance lets you plumb a shared argument to a number of functions. Here's a contrived example:
(++) <$> map toUpper <*> reverse $ "Hello" "HELLOolleH"
-R
[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.
[2]: Actually, it turns out that one only needs to prove the first law for
fmap because the second law is implied by the first, but that's a topic for
another day!
On Sat, Jun 4, 2016 at 5:11 PM Gesh
On 2016-06-04 19:56, Daniel Bergey wrote:
I think "a functor is a container" is not so helpful. It works OK for Maybe and List, but it doesn't seem helpful in understanding Either, Reader, Writer, State, Continuation, promises. This is correct. However, a large class of types form what are called "Representable Functors". These include Lists, Trees, ((->) r), etc.
toFunction xs = \i -> xs !! i toList f = fromList $ map f [0..] I *think* it's the case that for (r ->), there isn't anything we can do with the Monad instance that we can't do with Applicative. If someone can confirm or refute that, I'd appreciate it. That's of course not true in general for other monads. Indeed, for any representable functor, this all follows from the fact
A representable functor is any type f with an isomorphism `(f a ~ r -> a)` for some r. For example, `Stream a ~ Natural -> a` under the isomorphism: that we can write a lawful join from Reader's <*>. Letting `join m = flip ($) <*> m`, we have:
(join . pure) x = \r -> ($ r) (const x r) = \r -> x $ r = x (join . fmap pure) x = \r -> ($ r) ((pure . x) r) = \r -> (const (x r)) r = \r -> x r = x (join . fmap join) x = \r -> ($ r) ((join . x) r) = \r -> join (x r) r = \r -> (\s -> ($s) (x r s)) r = \r -> x r r r = \r -> ($r) (\s -> x s s) r = join (\s -> ($s) (x s)) = (join . join) x
Hence, given the applicative instance for Reader, we obtain the Monad instance for free. Therefore, working under the isomorphism, we have the same for any representable functor.
In particular, this gives that Stream is a Monad, where return gives the constant stream and join takes the diagonal of a stream of streams.
Again, as noted, this is more or less the only way in which the "Functors/Applicatives/Monads are nice/nicer/nicest containers" analogy works. There are more things in heaven and earth than are described in that analogy, but it's a start.
Hope this helps, and that it lacks errors/misleading material, Gesh P.S. Code for working with representable functors can be found in representable-functors. Code for working with Streams can be found in streams. Both are on Hackage. _______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
participants (4)
-
Daniel Bergey -
Gesh -
Raja -
Rein Henrichs