haskell, is IO Monoid associativity broken?

Question

In haskell IO type has instance of Monoid:

instance Monoid a => Monoid (IO a) where
    mempty = pure empty

if I have three actions which share some state, and change behavior of each other via side effect, this can lead to breaking associativity law, from IO type point of view:

a1:: IO String
a2:: IO String
a3:: IO String

(a1 mappend a2) mappend a3 /= a1 mappend (a2 mappend a3)

for example if a1,a2,a3 request current time in string, or IO contains some DB which counts for request number. This mean that it can be:

(a1 `mappend` a2) `mappend` a3  == "1"++"2"++"3"
a1 `mappend` (a2 `mappend` a3) == "3"++"1"++"2"

EDIT:

I think I shouldn't have given an example with a db, it confused, more preferred example:

a1 = show <$> getUnixTime 
a2 = show <$> getUnixTime
a3 = show <$> getUnixTime

l = (a1 `mappend` a2) `mappend` a3
r = a1 `mappend` (a2 `mappend` a3)
liftA2 (==) l r
**False**

So why IO type is monoid if it can break associativity law? or I missing something?

Answer 1

a1 `mappend` (a2 `mappend` a3) does not run in the order a2, a3 and a1. In contrast to imperative languages like Python for example, in Haskell an IO a is not some result of a computation, it is a recipe to produce a value of a. You can actually see an IO more like a continuation in Python, you pass a function such that eventually it can be called, but you do not call it directly.

The mappend function is implemented as liftA2 (<>) for the Semigroup a => Semigroup (IO a) instance, as we can see in the source code:

instance Semigroup a => Semigroup (IO a) where
    (<>) = liftA2 (<>)

This thus means that mappend is implemented as:

mappendIO :: Semigroup a => IO a -> IO a -> IO a
mappendIO f g = do
    x <- f
    y <- g
    pure (x <> y)

so it runs f before g.

If we now look at (a1 `mappend` a2) `mappend` a3, we see:

(a1 `mappend` a2) `mappend` a3 = do
    x <- do
        x1 <- a1
        x2 <- a2
        pure (x1 <> x2)
    y <- a3
    pure (x <> y)

which is equivalent to:

(a1 `mappend` a2) `mappend` a3 = do
    x1 <- a1
    x2 <- a2
    x3 <- a3
    pure ((x1 <> x2) <> x3)

If we then look at a1 `mappend` (a2 `mappend` a3) then this is equivalen to:

a1 `mappend` (a2 `mappend` a3) = do
    x <- a1
    y <- do
        y1 <- a2
        y2 <- a2
        pure (y1 <> y2)
    pure (x <> y)

which is equivalent to:

a1 `mappend` (a2 `mappend` a3) = do
    x1 <- a1
    x2 <- a2
    x3 <- a2
    pure (x1 <> (x2 <> x3))

Since x1 <> (x2 <> x3) is equivalent to (x1 <> x2) <> x3, this will thus return the same result in both items.

As for your test:

l = (a1 `mappend` a2) `mappend` a3
r = a1 `mappend` (a2 `mappend` a3)
liftA2 (==) l r
False

Notice that the liftA2 (==) again will define a sequence, so that means that your liftA2 (==) l r is defined as:

liftA2 (==) l r = do
    x1 <- a1
    x2 <- a2
    x3 <- a3
    y1 <- a1
    y2 <- a2
    y3 <- a3
    pure ((x1 <> x2) <> x3) == (y1 <> (y2 <> y3))

You thus run r after l.

If you make use of State monad, you can make it more clear what will happen, and validate if the rule is applied. You need to reset the state between l and r however.

Answer 2

You cannot use liftA2 (==) to meaningfully compare IO values: this comparison relation is not even reflexive!

Indeed, if we run

a1 = show <$> getUnixTime 
liftA2 (==) a1 a1

It is possible to get a False result, since time passes between the two calls to getUnixTime, so the returned value might differ.

This is even more clear if you define a1 to return the value of some random number generator. Calling that twice would yield a different result almost always.

Yet another example: liftA2 (==) getLine getLine can return false if the user enters two different lines.

When we say that ioAction1 is equal to ioAction2 we mean that they would have the same effect if executed in the exact same context. This is not the same as executing one action after the other and comparing the results.

Precisely defining "same IO effect" is tricky, though, since we usually want yo ignore performance differences. E.g. return () >> print True might be slightly slower than print True, if no optimization is performed, still we want to regard these two actions as having the same effects.