Haskell Monad bind currying

Question

I am currently in need of a bit of brain training and I found this article on Haskell and Monads

I'm having trouble with exercise 7 re. Randomised function bind.

To make the problem even simpler to experiment, I replaced the StdGen type with an unspecified type. So instead of...

bind :: (a -> StdGen -> (b,StdGen)) -> (StdGen -> (a,StdGen)) -> (StdGen -> (b,StdGen))

I used...

bind :: (a -> c -> (b,c)) -> (c -> (a,c)) -> (c -> (b,c))

and for the actual function impelemtation (just straight from the exercise)

bind f x seed = let (x',seed') = x seed 
                 in f x' seed'

and also 2 randomised functions to trial with:

rndf1 :: (Num a, Num b) => a -> b -> (a,b)
rndf1 a s = (a+1,s+1)

rndf2 :: (Num a, Num b) => a -> b -> (a,b)
rndf2 a s = (a+8,s+2)

So with this in a Haskell compiler (ghci), I get...

:t bind rndf2
bind rndf2 :: (Num a, Num c) => (c -> (a, c)) -> c -> (a, c)

This matches the bind curried with rndf2 as the first parameter.

But the thing I don't understand is how...

:t bind rndf2 . rndf1

Suddenly gives

bind rndf2 . rndf1 :: (Num a, Num c) => a -> c -> (a, c)

This is the correct type of the composition that we are trying to produce because

bind rndf2 . rndf1

Is a function that:

takes the same parameter type(s) as rndf1
AND takes the return from rndf1 and pipes it as an input of rndf2 to return the same type as rndf2

rndf1 can take 2 parameters a -> c and rndf2 returns (a, c) so it matches that a composition of these function should have type:

bind rndf2 . rndf1 :: (Num a, Num c) => a -> c -> (a, c)

This does not match the naive type that I initially came up with for bind

bind f :: (a -> b -> (c, d)) -> (c, d) -> (e, f)

Here bind mythically takes a function that takes two parameters and produces a function that takes a tuple in order that the output from rndf1 can be fed into rndf2

why the bind function needs to be coded as it is
Why the bind function does not have the naive type

What do you mean by "the correct type that we are eventually heading for"? If you mean type of unit, then it's wrong because unit :: a -> c -> (a,c) (note the missing Num contexts). — Vitus
@Vitus - I have added some extra clarification as to what types I am talking about together with a clarification of my actual question. Esentially my confusion is the same as Chris Bogart's from the original article's comments linked here — Chime

Enra Enra · Accepted Answer · 2012-06-27T21:08:24

bind should take two functions. Your "initial" type signature takes one function and one tuple and produces a tuple. That's not really applicable to this problem: rndf1 is not a tuple, it is a function. Once parameters have been applied to it, only then will rndf1 a s become a tuple. So bind needs to be a function that takes two functions.

The mysterious force that pipes a tuple into a function that takes two parameters is in the definition of bind.

bind :: (a -> c -> (b,c)) -> (c -> (a,c)) -> (c -> (b,c))
bind f x seed = let (x',seed') = x seed 
                 in f x' seed'

In this definition, both f and x are functions (maybe this would be more clear if you renamed x to g.)

Take let (x',seed') = x seed. x seed produces a tuple. On the left side of the equal sign, the individual elements of that tuple are given new names, and then on the next line those names are passed to the function f.

So, it may help to break down the expression bind rndf2 . rndf1.

Remember that all functions actually have exactly one parameter. The type of rndf1 could be written most accurately as (Num a , Num b) => a -> (b -> (a,b)). This is very helpful to understand what follows.

Another thing that would help is to think of how you would use this expression with parameters. Such as: (bind rndf2 . rndf1) a s.

Since all functions have one parameter, they're sent one by one to the inside of the parentheses. First: ((bind rndf2 . rndf1) a) s.

Now, you can rewrite the expression without the . operator: (bind rndf2 (rndf1 a)) s. a is passed to rndf1 because that is how . works: the function on the right side of the dot takes the input and then passes its output to the function on the left side.

You'll see that the type signature of rndf1 a matches the second parameter of bind. So then applying the parameters rndf2 and (rndf1 a) to bind:

bind rndf2 (rndf1 a) seed = let (x', seed') = (rndf1 a) seed
                             in rndf2 x' seed'

Now you have a function inside the parentheses that only takes one seed parameter. So you can take the s and apply it to the function:

bind rndf2 (rndf1 a) s = let (x', seed') = (rndf1 a) s
                          in rndf2 x' seed'

Haskell Monad bind currying

1 Answers