通过等式推理理解 Monad CountMe 的绑定

Question

这个问题来自“Haskell 从第一原则编程”一书的第 18.5 节“Monad 法则”的“坏 monad 及其居民”部分。

data CountMe a =
  CountMe Integer a
  deriving (Eq, Show)
instance Functor CountMe where
  fmap f (CountMe i a) =
    CountMe i (f a)
instance Applicative CountMe where
  pure = CountMe 0
  CountMe n f <*> CountMe n' a =
    CountMe (n + n') (f a)
instance Monad CountMe where
  return = pure
  CountMe n a >>= f =
    let CountMe n' b = f a
    in CountMe (n + n') b

我在理解 Monad CountMe 的绑定如何使用等式推理时遇到一些问题：

CountMe (n + n') b 成为 CountMe n b + CountMe n' b 成为 CountMe n b + f a

这是正确的吗？如果是这样，CountMe n b 会变成什么？

如果不能进行等式推理，我应该如何理解它是如何工作的？

  CountMe n a >>= f =
    let CountMe n' b = f a
    in CountMe (n + n') b

Answer 1

CountMe (n + n') b becomes CountMe n b + CountMe n' b

不，这第一步已经不正确了。如果不了解更多有关 n、n' 或 b.

的信息，您实际上无法在此处采取任何评估步骤

例如，如果您知道 n=5 和 n'=7，那么您可以说 CountMe (5+7) b 变成 CountMe 12 b。或者，如果您知道 b=const "abc" True，那么您可以说 CountMe (n + n') (const "abc" True) 变成 CountMe (n + n') "abc"。但就目前而言，您根本无法采取下一个评估步骤。

当然，您可以编写很多“未评估”等式，例如

CountMe (n + n') b = CountMe (0 + n + n') b
CountMe (n + n') b = CountMe (n + n') (if True then b else "mugwump")

等等，但不清楚它们中的任何一个对于理解 bind 的作用是特别令人兴奋或有用的方程式。

Answer 2

当您试图证明一个函数满足某个定律，或者两个表达式计算出相同的值，或者某个类似的假设时，等式推理很有用。等式推理无法综合理解函数的工作原理——你必须从一个计划开始。如果你只是想弄清楚一个函数的作用，最好的方法就是阅读代码！

举一个等式推理可以做的事情的例子，假设我们想确定CountMe的Monad实例是否满足“左身份”法，

return x >>= f = f x

这是计划。我们将从表达式 return x >>= f 开始，并尝试使用等式推理将其转换为 f x。

return x >>= f
CountMe 0 x >>= f                             -- definition of return
let CountMe n' b = f x in CountMe (0 + n') b  -- definition of (>>=)
let CountMe n' b = f x in CountMe n' b        -- 0 + n' = n'
f x                                           -- let pat = x in pat <-> x

就其价值而言，您的 CountMe monad 是 Writer monad (specifically, Writer (<a href="https://hackage.haskell.org/package/base-4.15.0.0/docs/Data-Monoid.html#t:Sum" rel="nofollow noreferrer">Sum</a> Integer)) 的示例。简而言之，Writer 计算在计算结果时建立一个幺半群的“对数”值；在这种情况下，“log”值是一个 Integer，而“building up”的概念是加法。

Answer 3

理解定义的一个好方法是想出一些绑定参数并尝试将其应用于它们。（我觉得这还是算作等式推理，只是它的一种简单形式做的是减少表达式。）

专用于 CountMe 的 >>= 类型是

CountMe a -> (a -> CountMe b) -> CountMe b

让我们尝试将 a 设为 Int，将 b 设为 Bool。

CountMe Int -> (Int -> CountMe Bool) -> CountMe Bool

对于第一个参数，我们想要一个 CountMe Int，我们称它为 x 和说：

x = CountMe 42 4

我们的第二个参数需要一个函数，所以我只写一个：

myfunc :: Int -> CountMe Bool
myfunc i = CountMe 37 (even i)

(even 是 Prelude 中的函数，用于检查数字是否甚至。）

现在我们可以计算 x >>= myfunc 看看会发生什么：

  x >>= myfunc
=                                         definition of x
  CountMe 42 4 >>= myfunc
=                                         definition of >>=,
                                          substituting in n=42, a=4, f=myfunc
  let CountMe n' b = myfunc 4
  in CountMe (42 + n') b
=                                         definition of myfunc with i=4
  let CountMe n' b = CountMe 37 (even 4)
  in CountMe (42 + n') b
=                                         definition of even
  let CountMe n' b = CountMe 37 True
  in CountMe (42 + n') b
=                                         pattern match gives n'=37, b=True,
                                          substitute these into body of let
  CountMe (42 + 37) True
=                                         arithmetic
  CountMe 79 True

这就是它的作用之一。你想尝试更多吗您可能需要编写其他函数作为示例绑定的第二个参数。（pure 可能适合那里作为一种可能性我认为。我不知道你是否被赋予了任何其他功能正确的形状。）

通过等式推理理解 Monad CountMe 的绑定

Understanding Monad CountMe's bind through equational reasoning

monads

haskell