haskell - Haskell 中的 monad 函数 dist 和 join 之间有什么关系？

Question

我在做函数式编程类(class)的作业之一时，发现在理解 Haskell 中的 monad 时遇到了一些问题。

所以，我们得到了一个类型:

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

任务是用给定的类型签名实现一些函数，我做到了。他们通过了所需的测试(分别):

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

然而，我们还被要求满足以下等式:

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

我无法完全理解这么多函数应用程序，所以对于具有类似任务的其他类型，我只是做了看起来“自然”的事情并且它有效，但在这里它没有而且我不明白为什么，因为我什至没有看到其他方法来实现这些功能。我错过了什么？

Answer 1

让我们从麻烦的方程式开始，系统地替换定义，从里到外计算:

-- 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

因此，问题是 distAnnotated以与 joinAnnotated 不同的顺序组合注释( m <> n 对比 n <> m )。让他们同意的通常方法是改变joinAnnotated以便外部注释排在第一位:

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

这既符合单子(monad)绑定(bind)中的自然计算顺序 (m >>= f = joinAnnotated (mapAnnotated f m))，也符合传统的从左到右的应用效果顺序 (p <*> q = ap p q = mapAnnotated (\(f, a) -> f a) (distAnnotated (p, q)))。