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 bMonad m => ((->) r) a -> (a -> ((->) r) b) -> ((->) r) bMonad m => (r -> a) -> (a -> (r -> b)) -> r -> bMonad 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 replicatereplicate :: 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 lengthlength :: [a] -> IntPrelude> :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])`

` 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`