f, g, h :: Kleisli ((->) e) a b <=> f >>> (g &&& h) = (f >>> g) &&& (f >>> h)?

Question

Edit: We will call an arrow p pure if exists such function f that: p = arr f.

I'm trying to get a better grasp of Arrows in Haskell, and I want to figure out when

f >>> (g &&& h) = (f >>> g) &&& (f >>> h), where f, g, h are arrows.

Obviously, it isn't generally true. In this particular example, the side-effects are duplicated on the right hand:

GHCi> c = Kleisli $ \x -> ("AB", x + 1)
GHCi> fst . runKleisli (c >>> c &&& c) $ 1
"ABABAB"
GHCi> fst . runKleisli ((c >>> c) &&& (c >>> c)) $ 1
"ABABABAB"

Obviously, f >>> (g &&& h) = (f >>> g) &&& (f >>> h) if f is pure.

I was experimenting in GHCi with this statement for f, g, h :: Kleisli ((->) e) a b, and didn't manage to find such values of f, g and h that f >>> (g &&& h) ≠ (f >>> g) &&& (f >>> h). Is this statement indeed true for f, g, h :: Kleisli ((->) e) a b, and, if so, could this be a valid proof of that: The effect of the Monad ((->) e) is reading from the environment. Thus, the result of the application of f is the function with the help of which g and h are going to read from the environment. No matter where this function was created – it is the same since it is applied to the same argument every time, thus the result of reading from the environment is the same, thus the overall result is the same as well.

Interesting follow-up question: which are the monads that have this property? Are all of them isomorphic to a combination of `Reader` and `Writer` with an [idempotent](https://en.wikipedia.org/wiki/Idempotence) monoid? — leftaroundabout, Aug 13 '19 at 11:56
@leftaroundabout I'm pretty sure we can add `Either` and `Maybe` Monads to the list since their effect depends on the sequence of applications, and, according to the definition of `(&&&)`, the applications are the same and are in the same order on the left hand and the right hand. But I might be mistaken. What do you think? — Zhiltsoff Igor, Aug 13 '19 at 14:13

chi · Accepted Answer · 2019-08-13T07:27:33.773

Intuitively

Yes, the (->) e monad is a reader monad, and it does not matter if we perform two reads or only one. Running f once or twice does not matter, since it will always produce the same result, with the same effect (reading).

Your reasoning seems intuitively correct to me.

Formally

f, g, h :: Kleisli ((->) e) a b essentially means f, g, h :: a -> (e -> b), removing the wrapper.

Again, ignoring the wrapper, we get

for all (f :: a -> e -> b) and (g :: b -> e -> c)
f >>> g = (\xa xe -> g (f xa xe) xe)

for all (f :: a -> e -> b) and (g :: a -> e -> c)
f &&& g = (\xa xe -> (f xa xe, g xa xe))

Hence:

f >>> (g &&& h)
= { def &&& }
f >>> (\xa xe -> (g xa xe, h xa xe))
= { def  >>> }
(\xa' xe' -> (\xa xe -> (g xa xe, h xa xe)) (f xa' xe') xe')
= { beta }
(\xa' xe' -> (g (f xa' xe') xe', h (f xa' xe') xe'))


(f >>> g) &&& (f >>> h)
= { def >>> }
(\xa xe -> g (f xa xe) xe) &&& (\xa xe -> h (f xa xe) xe)
= { def &&& }
(\xa' xe' -> ((\xa xe -> g (f xa xe) xe) xa' xe', (\xa xe -> h (f xa xe) xe) xa' xe'))
= { beta }
(\xa' xe' -> (g (f xa' xe') xe', h (f xa' xe') xe'))

Do `Either` and `Maybe` Monads also have this property? I believe they do since their effect depends on the sequence of applications, and, according to the definition of `(&&&)`, the applications are the same and are in the same order on the left hand and the right hand. — Zhiltsoff Igor, Aug 14 '19 at 09:02

f, g, h :: Kleisli ((->) e) a b <=> f >>> (g &&& h) = (f >>> g) &&& (f >>> h)?

1 Answers1

Intuitively

Formally