Haskell monad 返回任意数据类型

Question

我在定义自定义递归数据类型的返回时遇到问题。

数据类型如下:

数据 A a = B a | C (A a) (A a)

但是，我不知道如何定义 return 语句，因为我不知道何时返回 B 值以及何时递归返回 C。

感谢任何帮助!

Answer 1

为此类型定义 Monad 实例的一种方法是将其视为自由 monad。实际上，这将 A a 视为一种带有一个二元运算符 C 的小语法，并且变量由嵌入的 a 类型的值表示。 B 构造函数。这使得 返回 B 构造函数、嵌入变量和 >>= 执行替换的运算符。

instance Monad A where
  return = B
  B x   >>= f = f x
  C l r >>= f = C (l >>= f) (r >>= f)

不难看出 (>>= B) 执行恒等替换，并且替换的组合是关联的。

看待这个单子(monad)的另一种更“必要”的方式是，它捕捉了可以翻转硬币的计算思想(或读取比特流或以其他方式访问一系列二进制选择)。

data Coin = Heads | Tails

任何可以翻转硬币的计算都必须以一种方式停止翻转并成为一个值(使用 B)，或者翻转硬币并继续(使用 C)如果硬币出现正面，如果出现反面。抛硬币并告诉您出现了什么的一元操作是

coin :: A Coin
coin = C (B Heads) (B Tails)

A 的 >>= 现在可以被视为排序硬币翻转计算，允许后续计算的选择取决于先前计算提供的值计算。

如果您拥有无限的硬币流，那么(除了您非凡的好运气之外)您也很幸运能够对其值进行任何 A 计算，如下

data Stream x = x :> Stream x   -- actually, I mean "codata"

flipping :: Stream Coin -> A v -> v
flipping _             (B v)    = v
flipping (Heads :> cs) (C h t)  = flipping cs h
flipping (Tails :> cs) (C h t)  = flipping cs t

这种 monad 的一般模式是有一个用于返回值的构造函数(此处是 B)和一堆其他表示可能操作的选择以及计算可以继续的不同方式给定操作的结果。这里，C 没有非递归参数和两个子树，因此我可以判断，必须只有一个操作，并且它必须只有两个可能的结果，因此掷一枚硬币。

因此，它替代了带有变量和一个二元运算符的语法，或者是一种对翻转硬币的计算进行排序的方法。哪种观点更好？嗯...它们是同一枚硬币的两面。