Mon Oct 24 17:38:58 EDT 2011


Learning Haskell I sometimes get the wrong intuition..  An example: It
was not at first clear to me that these two are not the same.

      (CBN)   f mx my

      (CBV)   do
                x <- mx
                y <- mx
                f (return x) (return y)

Here I'm using the Call-By-Name (CBN) and Call-By-Value (CBV)
terminology from [1] to indicate the different meaning between the
two.  The first one passes two (named) computations to f, while the
second one passes two values (they are monadic wrapped, but they are
"pure" due to the return).

The main difference is that in the second step, the sequencing has
already happened before f is invoked.

Now why is this?  It's probably simpler to see with a single case.

Why are these two expressions not always the same?

    mx >>= \x -> f $ return x

    f mx

The answer is that there is absolutely no reason they should be, and I
don't understand why I had the idea in the first place.  From the
perspective of f the two cases are vastly different.  In the former f
will always get a value that's the result of a return, which means it
is "simple" or "pure", while in the latter f can receive a value that
could be more complex.

Here's a counterexample using the list monad that illustrates this
difference.  The first test passes a one element list to f and does
that 3 times, collecting the result of each evaluation in a list.  The
second test just passes the list.

  t1, t2 :: Monad m => (m a -> m b) -> m a -> m b
  t1 f mx = mx >>= (\x -> f (return x))
  t2 f mx = f mx

  f l = [length l]
  l = [1,2,3]

  (t1 f l, t2 f l)  -- ([1,1,1],[3])

[1] http://homepages.inf.ed.ac.uk/wadler/papers/essence/essence.ps.gz