[Haskell-cafe] evaluation semantics of bind

[Jake McArthur]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Gregg Reynolds wrote:
| As I understand it, a monad is a kind of programming trick the uses
data dependency to force evaluation order.

Actually, a monad does nothing more than supply some combinators. These
combinators (and some trivial laws) are all you really need to know to
understand monads. Specific monads are really just a case-by-case issue.

Using some function names that are not used in the standard Haskell
libraries, here are the important functions you have access to when you
have a monad, all of which return monadic values:

~    point ::                   a -> f a
~    map   ::   (a ->   b) -> f a -> f b
~    apply :: f (a ->   b) -> f a -> f b
~    bind  ::   (a -> f b) -> f a -> f b

I aligned the type signatures the way I did so you could see their
similarities and differences more easily.

point is the same as the return and pure functions. It lifts a pure value.

map is the same as the (<$>), fmap, liftA, and liftM functions. It
applies a pure function to a lifted value.

apply is the same as the (<*>) and ap functions. It applies a lifted
function to a lifted value.

The type signature for bind is reversed from that of (>>=). It's the
same as (=<<). I think it is more clear and better parallels the other
functions I've already shown. It applies a "lifting" function to a
lifted value.

| since the value of f x depends on the value of x, the evaluator must
evaluate x before f x

This is actually not true. Remember, Haskell is a lazy language. x need
not be evaluated before applying f to it.

| However, consider:
|
|     getChar >>= \x -> getChar
|
| An optimizer can see that the result of the first getChar is discarded
and replace the entire expression with one getChar without changing the
formal semantics.

Consider how this expression would actually look in a Haskell program:

~    main :: IO ()
~    main = getChar >>= \x -> getChar

Remember, a type coincides with a value. That is, the entire main
function is a _value_ of type IO (). The value, as it so happens, is an
imperative program which the Haskell runtime performs. That is, the
reduction semantics of IO expressions _produce_, rather than perform,
actions. The actions are only performed by the runtime. Every monad has
a "run" function. The IO monad's run function is the Haskell runtime.

If you think of the IO monad as some sort of Writer monad, it is easy to
see that Haskell's reduction semantics actually guarantee correct order
of operations, and a semantics-preserving optimizer will not change it.

In GHC, the IO monad is actually more like a State monad (over
RealWorld). It is also easy to see that this preserves correct ordering
of side-effects as well. I just wanted to present a different point of view.

- - Jake
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkmLDpMACgkQye5hVyvIUKnUpwCfdAycTBv29wVt+J5VHZbNEQ3H
80kAnj7u7HS+5S1qxgzB90I7v+ftuazo
=poXT
-----END PGP SIGNATURE-----