What is the relationship between monad functions dist and join in Haskell?-CodePudding

I was doing one of the homeworks from functional programming course and found some problems understanding monads in Haskell.

So, we were given a type:

data Annotated e a = a :# e
infix 0 :#

The task was to implement some functions with given type signatures, which I did. They pass needed tests (separately):

mapAnnotated :: (a -> b) -> (Annotated e a -> Annotated e b)
mapAnnotated f (x :# w) = f x :# w

joinAnnotated :: Semigroup e => Annotated e (Annotated e a) -> Annotated e a
joinAnnotated ((b :# m) :# n) = b :# m <> n

distAnnotated :: Semigroup e => (Annotated e a, Annotated e b) -> Annotated e (a, b)
distAnnotated (x :# m, y :# n) = (x, y) :# m <> n

However, we were also asked to satisfy following equation:

distAnnotated (p, q) = joinAnnotated (mapAnnotated (\a -> mapAnnotated (\b -> (a, b)) q) p)

I can't quite get my head around so many function applications, so for other types with similar tasks I just did what seemed "natural" and it worked, but here it doesn't and I can't see why, since I don't even see other ways to implement these functions. What am I missing?

CodePudding user response：

Let's start with the troublesome equation and systematically substitute the definitions, working it inside-out:

-- Given
mapAnnotated f (x :# w) = f x :# w
joinAnnotated ((b :# m) :# n) = b :# m <> n
distAnnotated (x :# m, y :# n) = (x, y) :# m <> n
p = x :# m
q = y :# n

-- Goal
distAnnotated (p, q) = joinAnnotated (mapAnnotated (\a -> mapAnnotated (\b -> (a, b)) q) p)

-- Right-hand side
joinAnnotated (mapAnnotated (\a -> mapAnnotated (\b -> (a, b)) q) p)
joinAnnotated (mapAnnotated (\a -> mapAnnotated (\b -> (a, b)) (y :# n)) (x :# m))
joinAnnotated (mapAnnotated (\a -> (\b -> (a, b)) y :# n) (x :# m))
joinAnnotated (mapAnnotated (\a -> (a, y) :# n) (x :# m))
joinAnnotated (mapAnnotated (\a -> (a, y) :# n) (x :# m))
joinAnnotated ((\a -> (a, y) :# n) x :# m)
joinAnnotated (((x, y) :# n) :# m)
(x, y) :# n <> m
-- Left-hand side
distAnnotated (p, q)
distAnnotated (x :# m, y :# n)
(x, y) :# m <> n
-- LHS /= RHS

The problem, therefore, is that distAnnotated combines the annotations in a different order than joinAnnotated (m <> n versus n <> m). The usual way to make them agree is changing joinAnnotated so that the outside annotation comes first:

joinAnnotated ((b :# m) :# n) = b :# n <> m

This fits both the natural sequencing of computations in the monadic bind (m >>= f = joinAnnotated (mapAnnotated f m)) and the conventional left-to-right order of applicative effects (p <*> q = ap p q = mapAnnotated (\(f, a) -> f a) (distAnnotated (p, q))).