Cha*_*eow 7 haskell functional-programming
我是 Haskell 的新手，并试图更好地了解 monad 的结合律，其中规定：
m >>= (\x -> kx >>= h) = (m >>= k) >>= h
通过试图构建会违反该法律的虚假 monad。在高层次上，这条定律似乎是在强制对我应用“一元函数”（不确定是否有合适的术语）的关联性。特别是，它看起来像是在强制执行某些版本的 (fg) x = f(g(x))，转换为 monad。
然而，如果我们认为 f 和 g 是纯数学函数，那么这种关系似乎是微不足道的。这让我想知道如果不涉及 IO 是否有可能违反这条法律，因为以我目前对 Haskell 的基本了解，这将确保 f 和 g 没有副作用。
我希望有人能详细说明我的总体思路是否正确，或者我是否有一些关键的误解，并且可以在不使用 IO 的情况下构建这样一个反例。
我们集体历史中的一个标准例子是 ListT monad 转换器，它出人意料地很难*正确。wiki对明显的实现出了什么问题以及如何修复它进行了全面的讨论，我将在此处摘录。它使用以下看起来非常合理的“monad”实例：
newtype ListT m a = ListT { runListT :: m [a] }
instance (Monad m) => Monad (ListT m) where
return a = ListT $ return [a]
m >>= k = ListT $ do
a <- runListT m
b <- mapM (runListT . k) a
return (concat b)
instance (Monad m) => MonadPlus (ListT m) where
mzero = ListT $ return []
m `mplus` n = ListT $ do
a <- runListT m
b <- runListT n
return (a ++ b)
这是关联的反例：
Run Code Online (Sandbox Code Playgroud)a,b,c :: ListT IO () [a,b,c] = map (liftIO . putChar) ['a','b','c'] t1 :: ListT IO () t1 = ((a `mplus` a) >> b) >> c t2 :: ListT IO () t2 = (a `mplus` a) >> (b >> c)...运行
runListT t1打印“aabbcc”，而runListT t2打印“aabcbc”。
这个特殊的例子碰巧使用了IO，但它不是基本的；我们也可以使用ListT (Writer String)“monad”而tell不是putChar.
*这个困难导致我们拥有一个庞大的密切相关的图书馆家族；该系列包括 list-t、logict、iteratee、machines、pipe、conduit 和 streamly。
正如卡尔在评论中提到的，结合律1的纯等价物是：
f . (g . h) = (f . g) . h
当以这种方式表达时，一元结合律更明显地相关2：
f <=< (g <=< h) = (f <=< g) <=< h
在这种形式下f，g和h都是所谓的“Kleisi箭”，它们与象型功能，这方法a -> m b（对于一些a，m和b，你不必是多态是一个Kleisi箭头）。箭头（或“鱼”）运算符3被称为“Kleisi 组合”，是对正常函数组合的完美一元类比。
(.) :: (b -> c) -> (a -> b) -> (a -> c)
(<=<) :: (b -> m c) -> (a -> m b) -> (a -> m c)
现在，正如您所指出的，结合律对于纯函数是“微不足道的”。但那是因为只有一个函数组合运算符.，而且它实际上是结合的！结合性是运算符的属性，而不是函数；任何运营商？是关联的当且仅当f ? (g ? h) = (f ? g) ? h对于所有可能的 f、g 和 h。对于纯组合，我们只考虑一个 operator .，因此没有“搜索空间”来探索纯组合如何是非关联的。
但是每个单独的 monad 都有自己的定义<=<（通过>>=Monad 实例中的定义），所以这个问题看起来更有趣。事实上，单子关联法有点从关联一个不同的野兽的财产的.。的结合.性只是一个事实。对于 Haskell 程序员来说，monad 结合律是一种义务，而不是数学真理4。这是我们在编写Monad实例时必须确保坚持的事情。
现在，让我们尝试通过构建一个反例来打破它。我们想要一些错误的 monad M，例如对于某些 f、g 和 h：
f <=< (g <=< h) ? (f <=< g) <=< h
由于我们不等式的两边都是函数，我们可以通过找到函数产生不同结果的某个值来证明它们不相等。即我们真正想要的是（对于某些 f、g、h 和 x）：
(f <=< (g <=< h)) x ? ((f <=< g) <=< h) x
提醒一下，所涉及的事物类型将是：
x :: z
h :: z -> M a
g :: a -> M b
f :: b -> M c
现在，如果我们的“monad”M只是一个单一值 ( data M a = M a)的无聊包装，那么<=<最终的行为就像.（只是额外的包装和解包），但我们知道这. 是关联的，所以我们不能想出一个这样的反例。
M如果我们要打破 的结合性，我们需要更多的结构<=<。因此，让我们尝试类似的方法data M a = M a Integer，即带有额外整数的值类型。
所以我们的<=<运算符定义必须是这种形式5：
(<=<) :: (b -> M c) -> (a -> M b) -> (a -> M c)
f <=< g
= \a -> let M b gInt = g a
M c fInt = f b
in M c (fInt ? gInt)
在哪里 ？可以是Integer -> Integer -> Integer我们喜欢的任何函数6！
因此，做出这些选择后，让我们看看我们是否可以稍微处理一下我们原来的不等式。左手边：
(f <=< (g <=< h)) x
-- apply definition of <=< to outer expression
= (\a -> let M b ghInt = (g <=< h) a
M c fInt = f b
in M c (fInt ? ghInt)) x
-- apply lambda to x
= let M b ghInt = (g <=< h) x
M c fInt = f b
in M c (fInt ? ghInt)
-- apply definition of <=< to inner expression
= let M b ghInt = (\a' -> let M b' hInt = h a'
M c' gInt = g b'
in M c' (gInt ? hInt)) x
M c fInt = f b
in M c (fInt ? ghInt)
-- apply lambda to x
= let M b ghInt = let M b' hInt = h x
M c' gInt = g b'
in M c' (gInt ? hInt))
M c fInt = f b
in M c (fInt ? ghInt)
-- move inner let bindings to outer let
= let M b' hInt = h x
M c' gInt = g b'
M b ghInt = M c' (gInt ? hInt))
M c fInt = f b
in M c (fInt ? ghInt)
-- since M b ghInt = M c' (gInt ? hInt), apply b = c' and ghInt = (gInt ? hInt)
= let M b' hInt = h x
M c' gInt = g b'
M c fInt = f c'
in M c (fInt ? (gInt ? hInt))
-- rename b' -> a, c' -> b, for ease of reading
= let M a hInt = h x
M b gInt = g a
M c fInt = f b
in M c (fInt ? (gInt ? hInt))
现在让我们试试不等式的右手边：
((f <=< g) <=< h) x
-- apply definition of <=< to outer expression
= (\a -> let M b hInt = h a
M c fgInt = (f <=< g) b
in M c (fgInt ? hInt)) x
-- apply lambda to x
= let M b hInt = h x
M c fgInt = (f <=< g) b
in M c (fgInt ? hInt)
-- apply definition of <=< to inner expression
= let M b hInt = h x
M c fgInt = (\a' -> let M b' gInt = g a'
M c' fInt = f b'
in M c' (fInt ? gInt)) b
in M c (fgInt ? hInt)
-- apply lambda to b
= let M b hInt = h x
M c fgInt = let M b' gInt = g b
M c' fInt = f b'
in M c' (fInt ? gInt)
in M c (fgInt ? hInt)
-- move inner let bindings to outer let
= let M b hInt = h x
M b' gInt = g b
M c' fInt = f b'
M c fgInt = M c' (fInt ? gInt)
in M c (fgInt ? hInt)
-- since M c fgInt = M c' (fInt ? gInt), apply c = c' and fgInt = (fInt ? gInt)
= let M b hInt = h x
M b' gInt = g b
M c' fInt = f b'
in M c' ((fInt ? gInt) ? hInt)
-- rename b -> a, b' -> b, and c' -> c, for ease of reading
= let M a hInt = h x
M b gInt = g a
M c fInt = f b
in M c ((fInt ? gInt) ? hInt)
因此，将双方放在一起，我们得出了以下结论：
let M a hInt = h x
M b gInt = g a
M c fInt = f b
in M c (fInt ? (gInt ? hInt))
?
let M a hInt = h x
M b gInt = g a
M c fInt = f b
in M c ((fInt ? gInt) ? hInt)
仔细比较，您会发现除了final 的第二个参数M（“侧面的整数”）之外，一切都完全相同。而这一切都与对 f、g、h 和 x（或者实际上，它们的类型是什么）做出的特定选择无关；事实证明，我们不需要知道，无论如何，我们的M和<=<定义都产生了这种形式。（如果我们只包装一个值，你应该能够明白我的意思，如在data M a = M a; 在这种情况下，类型迫使我们具有关联性，因为我们最终只是实现了与纯组合.运算符相同的东西）
我们实际上还没有决定什么？操作还没有，但比较fInt ? (gInt ? hInt)vs(fInt ? gInt) ? hInt只是关联性的定义！因此，我们要让不等式成立（因此要使M's<=<是非关联的）是整数上的任何非关联运算符。减法和除法都是非关联的；我相信你可以想出无数其他的。
因此，对于这种形式7（带有额外整数的值）的提议的 monad 来说，实际上很难通过关联性要求；我们必须仔细确保我们以关联的方式组合整数（因为有很多非关联的整数运算）。任何非关联操作都会产生这种形式的假单子。
显然，可以是 monad 的类型有各种各样的形式，我只是为了找到一个简单的反例（实际上找到了整个系列）而跳到了一个非常简单的形式。但是我们在这个表格中发现的内容确实适用于更普遍的情况；的关联性<=<不会在您编写Monad实例时自动发生，您必须仔细确保它成立。很可能（而且很容易）违反这条法律。关联性通常会很自然地从类型中脱离出来，这会让您误以为它总是成立，但事实并非如此。
1而不是(f.g) x = f(g(x))，正如问题中所猜测的那样。
2就>>=您用来直接创建 Monad 实例的运算符而言，该定律是：m >>= (\x -> k x >>= h) = (m >>= k) >>= h，它是等效的，但由于需要显式编写 lambda，因此看起来有点笨拙。
3你可以<=<在你的 Haskell 代码中使用这个运算符；它在Control.Monad 中。
4作为程序员，我们强制要求 monad 结合性，因为 monad 的结合性实际上是一个数学事实。在数学中，如果<=<您正在查看的操作符不是关联的，它只是表明您所拥有的不是 monad。在 Haskell 中，没有什么能阻止你编码一个Monad实例，而是>>=以一种<=<非关联的方式定义。但是我们想使用数学单子的理论来编写适用于所有Monads 的通用代码；结合性义务确保我们的Monads 也是数学单子。
5这意味着>>=在 Monad 实例中一定是这样的：
(M x i) >>= f
= let M y j = f x
in M y (j ? i)
6希望你可以看到a，b和c不得不去的地方，他们做的，因为<=<是多态的，并且没有其他的方式来获得类型的值c的最终结果，但fInt和gInt值是已知的Integer，所以我们可以做任何我们喜欢他们；我们甚至可以通过选择类似的东西来组成一个任意的返回值_ ? _ = 37。
7您可能已经注意到，这种形式与 Writer monad 的形式几乎完全相同，只是我锁定了“log”值Integer而不是将其作为类型参数保留。我实际上并不需要这样做，因为我也没有使用Integer（除了非关联操作的存在之外）的任何属性，我只是想避免添加更多变量！但这正是 Writer monad 实例Monoid对 log 值有约束的原因；它需要知道用于组合对数值的关联操作，以便传递 monad 的关联性要求（以及需要类似mempty“初始化” pure/ 中的对数值之类的东西return）。