The ((->) a) Monad instance (aka Function monad)

Today on #haskell@freenode I had this interesting discussion. I started with the question:

could anyone explain to me how is replicate >>= id equal to \x -> replicate x x?

And ended up with the answer:

f >>= id = (\x -> f x x) whenever f is a function

But let’s dig through the whole process and see how this magic is done.

First, let’s check the type of the bind operator (>>=):

Prelude> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

And let’s check how bind is defined for ((->) r) Monad:

instance Monad ((->) r) where  
return x = \_ -> x
h >>= f = \w -> f (h w) w

Next, let’s check the type of (replicate >>=):

Prelude> :t (replicate >>=)
(replicate >>=) :: ((a -> [a]) -> Int -> b) -> Int -> b

Patterns emerge. If we set m = ((->) r), we get:

Monad m => m a -> (a -> m b) -> m b
Monad m => ((->) r) a -> (a -> ((->) r) b) -> ((->) r) b
Monad m => (r -> a) -> (a -> (r -> b)) -> r -> b
Monad m => (r -> a) -> (a -> r -> b) -> r -> b

So, if we try to construct a function from this type, we understand from the type that it’s a function that takes 3 parameters, where the first two parameters are functions.

But before we go into that, how did we know that we should set m = ((->) r) in the first place?

From replicate’s type, we get:

Prelude> :t replicate
replicate :: Int -> a -> [a]

So, we have: Int -> (a -> [a]) = (->) Int (a -> [a]) = ((->) Int) (a -> [a])
And the generalization of that: ((->) r) (a -> [a])

So, back to our construction for f: we know that it should look something like: f x y z = ?
But from its type, we can see that the first parameter accepts an ‘r’ as input, and the second parameter accepts an input of the form (a -> r).

So we have something like: f x y z = y (x z) z (which is equivalent to the bind operator that we’ve shown before for the ((->) r) Monad instance)

So, if we apply replicate and id to f, we get: f replicate id z = id (replicate z) z f z = id (replicate z) z which equals to replicate z z

Now we can play with our function!

Prelude> f 3
Prelude> f 4
Prelude> f 5
Prelude> map (\x -> replicate x x) [1..10]
Prelude> concat $ map (\x -> replicate x x) [1..10]
Prelude> concat $ map (replicate >>= id) [1..10]
Prelude> concatMap (replicate >>= id) [1..10]
Prelude> concatMap f [1..10]

E.g.: Try to understand how it will work for “length”, for instance.

We have that:

Prelude> :t length
length :: [a] -> Int
Prelude> :t (length >>=)
(length >>=) :: (Int -> [a] -> b) -> [a] -> b

So, by looking at the definition for ((->) r) Monad, can you see what it does? Here are some hints:

Prelude> let f x y = (x, y)
Prelude> (length >>= f) [1,2,3]

Helpful excerpt from LYAH:

The implementation for >>= seems a bit cryptic, but it’s really not all that. When we use >>= to feed a monadic value to a function, the result is always a monadic value. So in this case, when we feed a function to another function, the result is a function as well. That’s why the result starts off as a lambda. All of the implementations of >>= so far always somehow isolated the result from the monadic value and then applied the function f to that result. The same thing happens here. To get the result from a function, we have to apply it to something, which is why we do (h w) here to get the result from the function and then we apply f to that. f returns a monadic value, which is a function in our case, so we apply it to w as well.

The full log:

 could anyone explain to me how is replicate >>= id equal to \x -> replicate x x
@type (>>=)
Monad m => m a -> (a -> m b) -> m b
bor0: With m = ((->) r), what is the specialized type of (>>=)?
r -> a -> (a -> (r -> a) b) -> r -> b ?
It’s (->) r a -> (a -> (->) r b) -> (->) r b
I can't understand prefix arrow
what does that mean?
Which is (r -> a) -> (a -> r -> b) -> r -> b
parentheses are important
(+) 4 5 = 4 + 5
(->) r a is (r -> a)
(r -> a) -> (a -> r -> b) -> r -> b
bor0: Can you come up with a definition for the function
f :: (r -> a) -> (a -> r -> b) -> r -> b?
(keep in mind that a -> b -> c is really a -> (b -> c) )
I can see that it takes three parameters, the first two being another function
bor0: Correct
hint: there is only one way to write it
isn't that just (.)?
identity: no
or foo f f1 = f1 . f?
f x y z = z x y ?
bor0: It must return a “b”. Which parameter can you use to get a b?
the y in "f x y z"
bor0: Correct. f ra arb r = arb something something
oh right, so f x y z = y x z?
stop guessing
bor0: You’ll need to apply it to something of type a and something of type r. Can you figure out
ion: is this correct? f x y z = y (x z) z
:t let f x y z = y (x z) z in f
(t2 -> t1) -> (t1 -> t2 -> t) -> t2 -> t
Kinda messy with the t's, but that's the same as: (r -> a) -> (a -> r -> b) -> r -> b
bor0: Yes. Congrats. Now, what is f replicate id?
So you got it
f z = id (replicate z) z
I got it from here
thank you. but, can you please explain to me the (-> r) part? what did you do there?
Your original expression replicate >>= id uses the Monad instance for ((->) r). Have you
learned about Monads?
I only know about monads in general. how can I see that replicate >>= id uses ((->) r) monad
:t replicate
Int -> a -> [a]
:t (>>=)
Monad m => m a -> (a -> m b) -> m b
replicate :: (->) Int (a -> [a])
BoR0: In order for Int -> t -> [t] to unify with m a
@type (replicate >>=)
((a -> [a]) -> Int -> b) -> Int -> b
sorry, I still can't see how you extracted ((->) r) from that
Int -> (t -> [t]) = (->) Int (t -> [t]) = ((->) Int) (t -> [t])
ahhh right
@src sequence
sequence [] = return []
sequence (x:xs) = do v <- x; vs <- sequence xs; return (v:vs)
@src liftM2
liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }
bor0: This may or may not be helpful:
which matches against m a with m = ((->) Int) and a = (t -> [t])
> (do f <- replicate; n <- id; return (f n)) 5
BoR0: The function monad instance is one where "running" a function means applying it to the
parameter to which the whole function has been applied
BoR0: Check this out:
> (do f <- replicate; id f) 5
> (do x <- id; y <- reverse; z <- map toUpper; return (x,y,z)) "hello"
> join replicate 5
> sequence [id, (+2), (*2), (^2), (2^)] 5
f >>= id = (\x -> f x x) whenever f is a function

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s