[Haskell-cafe] Bind as a sequencing operator (Was: evaluation semantics of bind)

[Derek Elkins]

On Thu, 2009-02-05 at 11:47 -0700, mail at justinbogner.com wrote:
> Jake McArthur <jake at pikewerks.com> writes:
> > mail at justinbogner.com wrote:
> > | Oops, sent this off list the first time, here it is again.
> > |
> > | Jake McArthur <jake at pikewerks.com> writes:
> > |> mail at justinbogner.com wrote:
> > |> | Bind is a sequencing operator rather than an application operator.
> > |>
> > |> In my opinion, this is a common misconception. I think that bind would
> > |> be nicer if its arguments were reversed.
> > |
> > | If this is a misconception, why does thinking of it this way work so
> > | well? This idea is reinforced by the do notation syntactic sugar: bind
> > | can be represented by going into imperative land and "do"ing one thing
> > | before another.
> >
> > An imperative-looking notation does not make something imperative.
> >
> > Thinking of bind as sequencing really *doesn't* work very well. What
> > does bind have to do with sequencing at all in the list monad, for
> > example? What about the reader monad?
> >
> > - Jake
> 
> What doesn't bind have to do with sequencing in the list monad?
> Consider:
> 
>   [1..2] >>= return . (^2)
> 
> This says "generate the list [1..2] and then use it to generate a list
> of squares". It's more than just application, it's a description of a
> sequence of actions. The whole point of list comprehensions (which is
> the only reason to have a list monad, as far as I know) is to think
> of it this way rather than as an application of concatMap.
> 
> As for Reader, I don't know enough about it to say anything.

Jake is more or less right.

The Monad interface does nothing to enforce any particular evaluation
order.  The interface is, however, too narrow for you to express "do
these two things in an indeterminate order" so you are forced to choose
a particular linearization.  Commutative monads, such as Reader, could
relax that constraint, not that it would really mean much in many of
those cases.

Now, if we wanted to give a semantics for a call-by-value programming
language, which was exactly the sort of thing Moggi was thinking about
when he was talking about monads, then application would indeed
translate into exactly (flipped) (>>=).  So the expression (f x) in,
say, SML would be translated to (f =<< x) using some appropriate monad
to model the side-effects that ML supports.  Actually, a 'let' like
notation is often preferred as it matches better with lists of
statements more prettily than the equivalent of treating ; as const.
This is the source of the name 'bind' as, e.g. the ML, (let a = M in let
b = N in a+b) translates to (M >>= \a -> N >>= \b -> return (a+b)) and,
of course, do-notation is just a syntactic variant of this 'let'
notation.