15

When executing the IO action defined by someFun <$> (a :: IO ()) <$> (b :: IO ()), is the execution of the a and b actions ordered? That is, can I count on that a is executed before b is?

For GHC, I can see the IO is implemented using State, and also see here that it is an Applicative instance, but can't find the source of the actual instance declaration. Being implemented through State suggests that different IO effects need to be sequential, but doesn't necessary defines their ordering.

Playing around in GHCi seems that Appliative retains effect order, but is that some universal guarantee, or GHC specific? I would be interested in details.

import System.Time
import Control.Concurrent
import Data.Traversable
let prec (TOD a b) = b
fmap (map prec) (sequenceA $ replicate 5 (threadDelay 1000 >> getClockTime))

[641934000000,642934000000,643934000000,644934000000,645934000000]

Thanks!

ron
  • 9,262
  • 4
  • 40
  • 73
  • I guess this post contains useful info but I still have to digest it: http://pchiusano.blogspot.hu/2011/07/do-side-effects-really-need-total-order.html – ron Jan 10 '13 at 13:49
  • 4
    See http://hackage.haskell.org/packages/archive/transformers/0.3.0.0/doc/html/Control-Applicative-Backwards.html, which is an applicative transformer that reverses the order of effects. – Sjoerd Visscher Jan 10 '13 at 13:57

3 Answers3

18

It's certainly deterministic, yes. It will always do the same thing for any specific instance. However, there's no inherent reason to choose left-to-right over right-to-left for the order of effects.

However, from the documentation for Applicative:

If f is also a Monad, it should satisfy pure = return and (<*>) = ap (which implies that pure and <*> satisfy the applicative functor laws).

The definition of ap is this, from Control.Monad:

ap :: (Monad m) => m (a -> b) -> m a -> m b
ap =  liftM2 id

And liftM2 is defined in the obvious way:

liftM2 f m1 m2 = do { x1 <- m1; x2 <- m2; return (f x1 x2) }

What this means is that, for any functor that is a Monad as well as an Applicative, it is expected (by specification, since this can't be enforced in the code), that Applicative will work left-to-right, so that the do block in liftM2 does the same thing as liftA2 f x y = f <$> x <*> y.

Because of the above, even for Applicative instances without a corresponding Monad, by convention the effects are usually ordered left-to-right as well.

More broadly, because the structure of an Applicative computation is necessarily independent of the "effects", you can usually analyze the meaning of a program independently of how Applicative effects are sequenced. For example, if the instance for [] were changed to sequence right-to-left, any code using it would give the same results, just with the list elements in a different order.

C. A. McCann
  • 76,893
  • 19
  • 209
  • 302
  • Thank you! Do I correctly infer that if effect order is important for me and I want to be theoretical then I should use a Monad, but if I'm practical an Applicative will (usually, with care) fit? – ron Jan 10 '13 at 14:17
  • 2
    @ron: In practice, you can simply assume that `Applicative` instances will sequence left-to-right unless they loudly announce otherwise, as with the `Backwards` wrapper. Note that `Monad` instances can also be ambiguous in other ways--for example, the reversed `State` monad threads the state value backwards, but the type itself is identical to regular `State`. For another example, `[]` has two possible `Applicative` instances even aside from the sequencing order. You can't avoid relying somewhat on what the documentation says. – C. A. McCann Jan 10 '13 at 14:29
  • @C.A.McCann "*[...] you can usually analyze the meaning of a program independently of how Applicative effects are sequenced.*" Why? Isn't that only true for *commutative* applicative functors? In general, reordering Applicative effects can change the result dramatically. Here is one example: `myParser = (++) <$> foo <*> bar` where `foo` and `bar` are parsec `Parser String`. If I changed the sequencing to right-to-left, `myParser` would fail on on input string `"foobar"`. Wouldn't you agree, in this case, that reordering of effects has affected the meaning of the program? – jub0bs Jul 21 '15 at 08:44
4

Yes, the order is predefined by the Monad-Applicative correspondence. This is easy to see: The (*>) combinator needs to correspond to the (>>) combinator in a well-behaved Applicative instance for a monad, and its definition is:

a *> b = liftA2 (const id) a b

In other words, if b were executed before a, the Applicative instance would be ill-behaving.

Edit: As a side note: This is not explicitly specified anywhere, but you can find many other similar correspondences like liftM2 = liftA2, etc.

ertes
  • 41
  • 1
2

For the IO Applicative, this is certainly the case. But check out the async package for an example of an Applicative where in f <$> a <*> b the effects of a and b happen in parallel.

Ben Millwood
  • 6,754
  • 24
  • 45