[evincarofautumn]

I think that law is slightly too restrictive; there’s a useful class of Monad instances where it doesn’t hold: commutative monads, in which:

    x <- f
    y <- g

Is equal to:

    y <- g
    x <- f

Provided that “x” is not free in “g”. A good example is an async monad that provides concurrency in (<*>) and only blocks when there’s a data dependency in (>>=)—the result is the same regardless of evaluation order, but the implementations (and performance characteristics) are different. You could handwave it away by arguing that they’re “morally equivalent”, but I think it pays to be precise about properties like commutativity of actions.

[lmm]

> the result is the same regardless of evaluation order, but the implementations (and performance characteristics) are different. You could handwave it away by arguing that they’re “morally equivalent”, but I think it pays to be precise about properties like commutativity of actions.

You have to decide whether they're equivalent or they're not, and if they're not equivalent (for your purposes) you probably shouldn't provide both instances. If you implement <hnmarkupisbad> and ap but they're not equivalent, a future maintainer will get a nasty surprise sooner or later.

[evincarofautumn]

I mean if you can’t observe any difference from safe code, then despite having different intensional/operational definitions, they are extensionally equivalent, and that’s mostly what I care about.

The ApplicativeDo desugaring, which uses the Applicative combinator instead of bind in exactly the circumstance I described above, was added specifically to support this use case when we (at Facebook) were writing Haxl, which is just such an example of a commutative monad; it’s built on IO, but doesn’t expose IO to safe code, so there’s no way to observe the concurrency from inside Haxl.

Granted, I’m biased because I have a somewhat unpopular definition of “effect” and “side effect”—if an effect can’t be observed from code by a particular observer that is safe wrt some property, then to me it’s not a side-effect.

It’s pretty widely accepted that within an ST action, mutating an STRef is a side effect to any observers within that action, but from the POV of the caller, the code is pure and thus side-effect–free; but I argue that mutating an IORef within an IO action is also not side-effectful, say from the POV of another thread, if the IORef is never shared—e.g.:

    -- Morally equivalent to “pure 1”.
    do
      x <- newIORef (0 :: Int)
      modifyIORef' x (+ 1)
      pure x

Again, all I’m really saying is that you need to be precise about what model of effects you’re talking about, and what properties you guarantee re. safety, commutativity wrt other effects, &c.

[lmm]

> if you can’t observe any difference from safe code, then despite having different intensional/operational definitions, they are extensionally equivalent, and that’s mostly what I care about.

That's true if the only things you care about are the things that are visible from safe code. But if you care about performance characteristics (which is presumably the whole point of this kind of monad) then code that gives the same result but has different performance characteristics is not equivalent for your purposes.

Ultimately, if x and y are marked as equivalent then a future maintainer will expect to be able to blindly replace x with y - and by convention that's true of <hnmarkupisbad> and ap. So you shouldn't define <hnmarkupisbad> and ap in such a way that replacing one with the other will change important characteristics of the code - you should only make things look equivalent in your code if they are equivalent for your purposes.

[nybble41]

Was that last line supposed to be "readIORef x" instead of "pure x"? If you return the IORef then the result is equivalent to "newIORef 1", not "pure 1"—and newIORef does have observable side-effects. (Two IORefs are distinct even if they hold the same value.)