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

[3,3,3]

Prelude> f 4

[4,4,4,4]

Prelude> f 5

[5,5,5,5,5]

Prelude> map (\x -> replicate x x) [1..10]

[[1],[2,2],[3,3,3],[4,4,4,4],[5,5,5,5,5],[6,6,6,6,6,6],[7,7,7,7,7,7,7],[8,8,8,8,

8,8,8,8],[9,9,9,9,9,9,9,9,9],[10,10,10,10,10,10,10,10,10,10]]

Prelude> concat $ map (\x -> replicate x x) [1..10]

[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9

,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10]

Prelude> concat $ map (replicate >>= id) [1..10]

[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9

,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10]

Prelude> concatMap (replicate >>= id) [1..10]

[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9

,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10]

Prelude> concatMap f [1..10]

[1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,9,9,9,9

,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10]

Prelude>

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]

(3,[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 ?

errr

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 (.)?

no

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

:p

bor0: You’ll need to apply it to something of type a and something of type r. Can you figure out

how?

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

instance?

: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: http://heh.fi/haskell/functors/#function-instance

which matches against m a with m = ((->) Int) and a = (t -> [t])

> (do f <- replicate; n <- id; return (f n)) 5

[5,5,5,5,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

[5,5,5,5,5]

> (do x <- id; y <- reverse; z <- map toUpper; return (x,y,z)) "hello"

("hello","olleh","HELLO")

> join replicate 5

[5,5,5,5,5]

> sequence [id, (+2), (*2), (^2), (2^)] 5

[5,7,10,25,32]

...

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