Comments on A Neighborhood of Infinity: You Could Have Invented Monads! (And Maybe You Alr...

The best tutorial on Monads! - Thank you

2012-02-11T05:59:02.631-08:00

The best tutorial on Monads! - Thank you

For not being a Haskell programmer, I've read ...

2010-12-31T18:16:42.730-08:00

For not being a Haskell programmer, I've read a fair number of explanations of monads over the past year (I blame Reddit). So far, I've hit two that have helped; an eight-word definition ("Monads provide a generalized interface to sequential computation."), and your exposition I just tripped across.

You've managed to take something that is somewhat impenetrable when presented by others and make the concept not merely natural but truly inevitable once we reach a certain level of abstraction. I suspect this means you normally teach math.

Anyway, thank you for this.

Thanks a lot for a great tutorial. I've been...

2010-12-13T02:57:27.296-08:00

Thanks a lot for a great tutorial.

I've been searching for a while and this is the best one I've found so far, both in books and on the net.

This tutorial is a great introduction to monads as...

2010-11-17T15:40:04.427-08:00

This tutorial is a great introduction to monads as it starts with the problem and let the reader develop (or even invent) the solution. This helped me a lot, thanks!

Anonymous, The version I gave highlights a certai...

2010-08-19T07:24:19.904-07:00

Anonymous,

The version I gave highlights a certain symmetry in the signature. It's of the form X -> F a -> F b. That's slightly hidden in your version. Of course they are equivalent, but it's this symmetry I want people to notice.

Is it an academic convention to write your type si...

2010-08-18T22:07:57.774-07:00

Is it an academic convention to write your type signatures like this?

bind :: (a → StdGen → (b,StdGen)) → (StdGen → (a,StdGen)) → (StdGen → (b,StdGen))

It would be much, much more clear if you wrote it like this:

bind :: (a → StdGen → (b,StdGen)) → (StdGen → (a,StdGen)) → StdGen → (b,StdGen)

Obviously the two are equivalent but it looks like you intend for the first one to return a function rather than accept a third argument.

An excellent tutorial. It really helped me a lot i...

2010-07-02T05:47:46.971-07:00

An excellent tutorial. It really helped me a lot in understanding monads. The key was the 'bind' function with the more natural order of parameters compared to '>>='. The '*' operator really made clear what is going on, and it was really simple to define it in terms of 'bind'. I also liked that you created exercises to force me stop and think, thus helping in the understanding of the concept.

On the downside: the wording before the bind function of the random number example needs a little bit of improvement, exercise 7 was the most difficult because of it.

Bravo - what a great tutorial ! I've read abou...

2010-03-09T13:22:04.934-08:00

Bravo - what a great tutorial ! I've read about a dozen articles and not really understood Monads but this one really hits the nail. Thanks.

It would be better to change unit * f = f * unit =...

2010-03-04T04:34:11.699-08:00

It would be better to change unit * f = f * unit = f in the paragraph above Exercise Two into unit * f' = f' * unit = f'. And a space is missing in f'*g' in the same paragraph.

About the do notation, you basically said: do {le...

2009-11-24T01:23:04.451-08:00

About the do notation, you basically said:

do {let x = y; more code} ==>> (\x -> do more code) y

I was confused at first, until I performed the obvious beta reduction:

let x = y in do more code

This is actually closer to the original do notation, closer to the other rules, and I think a bit clearer.

Anyway, thank you. I now have a way to explain monads to my poor C++ colleagues.

Great post, really made monads easy to understand....

2009-08-06T04:35:31.952-07:00

Great post, really made monads easy to understand.

Any chance you could write the same sort of thing on call/cc ?

Nice tutorial, but I don't like "your fav...

2009-02-12T07:06:00.000-08:00

Nice tutorial, but I don't like "your favorite number" ;>

In the line "Where we previously used a pair like ...

2008-07-14T02:37:00.000-07:00

In the line "Where we previously used a pair like (a,s) we now use Writer (a,s) of type Writer Char.", shouldn't it be type Writer [Char]?

Thanks.

About the randomized functions: All the confusion ...

2008-06-05T16:34:00.000-07:00

About the randomized functions: All the confusion is due to Curry-Howard iso making it unclear what is an argument and what is the return value. Depending on your view you get two different monad types. When you say "The first element of the pair that f returns" it seems clear that you view f as a 2-argument function which returns a pair and thus that the monad type should be (a, StdGen), but your solution of bind is the one for monad type StdGen -> (a, StdGen) which results from viewing f as a function of one argument which returns a function.
Your choice of names x and x' in your definition of bind is VERY confusing. Might I suggest instead: bind f r = \s -> let (x, s') = r s in f x s'? Other suggested rewording:
"We now must work out how to compose two randomized functions, f and g. The pair that the function that is returned by g returns needs to be decomposed and passed in as input to f. So we can give this signature for bind:".
It would also be very good if you could explain what happens if you choose the monad type to be (a, StdGen) and why that is a bad idea (if it is).
Lastly, I do think you offer a very enlightening view of monads, so thank you.

knut,

The function you defined is called "c...

2008-02-01T17:44:00.000-08:00

knut,

The function you defined is called "composition of Kleisli arrows". I wrote a bit about it here: http://sigfpe.blogspot.com/2006/06/monads-kleisli-arrows-comonads-and.html

Great tutorial! I especially liked the comparison ...

2008-02-01T17:31:00.000-08:00

Great tutorial! I especially liked the comparison between binding and function composition. In fact, for your examples, I find the "f*g" notation more succinct than both using >>= directly and the do notation. So far I haven't found an equivalent operator in Haskell, so for now I'm using the following:

module MonadUtils where
(°) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
f ° g = (>>= f) . g

While probably not suitable for IO, it's a pretty neat way of writing stuff like

sixthrt' = sqrt' ° cbrt'
(x',w) = runWriter $ (f ° g ° h) x

Andrew,

Sorry that caused confusion. Just t...

2008-01-08T08:49:00.000-08:00

Andrew,

Sorry that caused confusion. Just treat the two symbols the same way. At that point I was still trying to figure out which symbol was better to use and hadn't settled for one or the other. If I get time I'll try to make it consistent.

One thing that confused me horribly about this pap...

2008-01-08T07:40:00.000-08:00

One thing that confused me horribly about this paper.

Sometimes you use "->" and sometimes "→", as in

(a → m b) -> (m a → m b)

I thought that there might be some difference.

Would it be too much to change this?

OK, I've typed
test x g = (bind addDigit) . (bi...

2007-11-14T13:22:00.000-08:00

OK, I've typed
test x g = (bind addDigit) . (bind shift) . addDigit
instead of
test = (bind addDigit) . (bind shift) . addDigit
Sorry for the interruption

Hi, I think that I finally got this monad stuff. B...

2007-11-14T13:12:00.000-08:00

Hi, I think that I finally got this monad stuff. But there's a problem when I try to run the example from the appendix. Here's the error message:
Couldn't match expected type `(Integer, StdGen)'
against inferred type `Integer -> StdGen -> (Integer, StdGen)'
In the expression: (bind addDigit) . ((bind shift) . addDigit)

Jonathan,

Yes, that's fine. On each line yo...

2007-10-20T12:55:00.000-07:00

Jonathan,

Yes, that's fine. On each line you're introducing a new x.

As an alternative to

> do
> le...

2007-10-20T12:53:00.000-07:00

As an alternative to

> do
> let x = 7
> y <- Writer (x+1,"inc\n")
> z <- Writer (2*y,"double\n")
> Writer (z-1,"dec\n")

I believe you could also write

> do
> let x = 7
> x <- Writer (x+1,"inc\n")
> x <- Writer (2*x,"double\n")
> Writer (x-1,"dec\n")

Is that right?

Now let's say how I want the modeled function beha...

2007-10-05T10:50:00.000-07:00

Now let's say how I want the modeled function behave.

I'll take the example of the list of associations of the form (x,x+1) which I'll name "inc".

The associations that "inc" models are of type (int,int) but to make the problem solvable, it internally includes a supplementary leading element in the tuple, so it is in fact internally:
(id,[(int,int)])
with an additional type representing the "id"entity of a solution. If this identity is known and is a solution to the "inc" function, then the list which which it is associated contains a single pair of type (int,int) and its value (x,y) satisfies the condition y=x+1.

When coding the function, I want to be able to store it as a list of binding conditions representing the associations as a binding condition defining the satisfied association precisely as:

[(id,x,x+1)]

(the effective value of the id does not matter, it should be hidden by some syntax sugar of the language)

and the function will also encode several solutions to allow the problems to be solved according to the values of the variables :
[(id,x,x+1)]
[(id,y-1,y)]

(here also the value of the id should not be needed for the problems we need to solve, as the compiled function will internally compute them.

So instead of encoding in the syntax the places where the id is present, we will assume that the syntax provides such sugar to do that, so that the function is can be written by just specifying in its definition:
[(x, x+1)]
OR
[(y-1, y)]

In other words "inc" is now defined precisely as a list of tuples that it considers equivalent:
[(x, x+1), (y-1, y)]

When "running" the function, we'll give similar list of tuples in input, the function will try to bind each tuple of its input with each tuple present in the list of its own definition, and if a match is found, it will return this matching tuple with the variables bounds in the list of tuples that are part of the solution.

For making matches, the internal binding made by the "running" function will look for free variables present in its internal list of solutions, so given the input [(z,4)] that contains a free variable z for our problem, it binds successively each tuple of the input, i.e. (z,4) with each tuple in the list of proposed solutions:

* the first solution is the tuple (x,x+1), so binding it with the input tuple (z,4) would require binding x with z (this is possible) and x+1 with 4 (i.e. z+1 with 4, but this won't work because you can't bind an expression containing free variables from the input to a constant that has no free variable); this first solution is then eliminated from the output

* the second solution proposed by "inc" is the tuple (y-1,y), and binding it with the input (z,4) is possible: y-1 is bound to z (possible because both expressions contain free variables, this is the same as an equation y-1=z) and the second element y of the solution is bound to 4, so now y=4, and the tuple (y-1=z,y=4) is part of the solution, this tuple can be reduced because now y is not free and can be eliminated: (4-1=z,4) so finally the solution is (3=z,4)

Finally the function returns the list of tuples [(3=z,4)] for the input [(z,4)], and this is exactly what we wanted to solve.

The language may need to eliminate parts that are equivalent between the input and output, to provide a more readable solution by just keeping "3=z", i.e. the solution to the problem where z was free is now binding z to a value according to the definition of the "inc" function to which it was given. So the final solution is [(3,4)]

In other words: inc [(z,4)] returns a [(3,4)] each solution being annotated with bindings (which are implicit here because they are part of the input/output parameters to the function in the same order, so the bining z=3 is implicit from the problem it had to solve)

The difference here is that we are not limited by the curryfication.

Such model will easily represent as a "function" any database table.

The function would be written effectively something like:

"inc" :: [(int,int)] -> [(int,int)]
return [(x,x+1)] union [(y-1,y)]

There are a few other missing syntaxic sugar here to make it work (notably, I used the term "list" everywhere when in fact the list is not ordered but is actually a "set" with no duplicate elements). This requires some more work to perform set operations (as suggested above when I introduced the word "union").

How can I represent this extended "function" in Haskel? Can a monad represent such thing?

Can you propose asolution in Haskell for the more ...

2007-10-05T09:44:00.000-07:00

Can you propose asolution in Haskell for the more general problem of computing the input of a function from its result?
This is the general problem of solving equations, and we know that there may be several solutions to the problem, that the simple concept of currying will not solve always, or that will solve returning multiple solutions.
The concept could however be modeled by stating that the function input can be solved as a list that may be empty.
Is there a way to extend the concept of currrying a function one step further so that functions are now treated only as a pair consisting of its input and its output, so that we can pass it either the input or the output and compute the missing element of the pair according to the function definition?
Under this interpretation, we would not make any semantic difference between the function inputs (whatever their number) and the function outputs (also whatever their numbers): they are just indexed elements of a tuple, and currying is just one way to model the association (although currying just favors only one direction of solving problem, from the first member of the tuple to the last member).

My idea is to be able to represent also, for example a database table (with unique rows) as a function, and each row in the table is a tuple of elements that can be either interpreted as inputs or outputs of a function, so that we can solve the problem of finding the value of a missing column by specifying the value of the other columns.

To model a database table with non unique rows, we could reuse the same, because every row in a database table also has an implicit supplementary column that makes the row unique: the row number. under this representation, the database table canbe viewed as a curried function that takes a row number and returns the matching row as a tuple. But it could also take the tuple as input and return a list of matching row numbers. This is what I meanin a generalized currying concept: not favoring any direction of resolution. And here the concept of Monads could help by allowing to get in the return of a problem the list of values we are looking for in its return, "monadized" with the rest of the other column values given to the problem, the monad itself representing the association.

Let's think about the type of such function:
* a table is now in fact an association whose type is a list of tuples of several types, one type for each column.
* to solve a problem with this table, we specify it also with a tuple (or list of tuples) filled with the values of the column we know, and the function matches it by binding the columns in the input list of tuples with its own internal list of tuples modeling each row in the table. When a match is found, the function returns this row in the list of inputs.
* now let's look at the function that takes a numeric input and return the input plus 1: its is similar as it can be viewed as anassociation of tuples of the form (x, x+1) so the function or table is modeled as a list of pairs. The problem it can solve would not only be the forward problem of finding a matching association (x,x+1) when we know the value of the first column x as a list of matching values for x+1, but also finding solutions for the reverse problem.
For forward problems, I want to be able to give to the function that internally stores the association as list of pairs, i.e. [(int,int)], feed it with a tuple of lists of type ([int],unknown) which represent the values we know, the function will perform the internal resolution by binding this input with its internal list of tuples and will return a tuple of lists filled with the values of the "unknow" elements.
so conceptually, the function I need is now of "type":
([int],unkown)->(???,[int])
but could also return just the list of its rows that match the input:
([int],unkown)->[(???,int)]
As there's no direction favored, the generalization of the problem will required using the more general problem of representing the problems we can solve with this function as:
[(int|unknown,int|unknown)]->[(int|unknown,int|unknown)]
in other words, the type of a problem with its solution according to a function is a pair of types, whose signature are both equals the type signature of the function itself!
Regading the function "+1" above, it is just a particular solution to the geneal concept represented in [(x,x+1)] as if it was a database table containing all the associations (as as list of tuples) between is input and its output.

Misleading wording in the paragraph already finger...

2007-09-13T16:48:00.000-07:00

Misleading wording in the paragraph already fingered above aside, this text is awesome! Honest thanks, you totally demystified monads to another HS newbie. And that's coming from a social sci major :) .

Comments on A Neighborhood of Infinity: You Could Have Invented Monads! (And Maybe You Alr...

The best tutorial on Monads! - Thank you

For not being a Haskell programmer, I've read ...

Thanks a lot for a great tutorial. I've been...

This tutorial is a great introduction to monads as...

Anonymous, The version I gave highlights a certai...

Is it an academic convention to write your type si...

An excellent tutorial. It really helped me a lot i...

Bravo - what a great tutorial ! I've read abou...

It would be better to change unit * f = f * unit =...

About the do notation, you basically said: do {le...

Great post, really made monads easy to understand....

Nice tutorial, but I don't like "your fav...

In the line "Where we previously used a pair like ...

About the randomized functions: All the confusion ...

knut,The function you defined is called "c...

Great tutorial! I especially liked the comparison ...

Andrew,Sorry that caused confusion. Just t...

One thing that confused me horribly about this pap...

OK, I've typedtest x g = (bind addDigit) . (bi...

Hi, I think that I finally got this monad stuff. B...

Jonathan,Yes, that's fine. On each line yo...

As an alternative to> do> le...

Now let's say how I want the modeled function beha...

Can you propose asolution in Haskell for the more ...

Misleading wording in the paragraph already finger...

knut,

The function you defined is called "c...

Andrew,

Sorry that caused confusion. Just t...

OK, I've typed
test x g = (bind addDigit) . (bi...

Jonathan,

Yes, that's fine. On each line yo...

As an alternative to

> do
> le...