2

我无法通过自定义定义的递归数据类型定义返回。

数据类型如下：

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

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

任何帮助表示赞赏！

4

2 回答 2

14

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

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

任何可以翻转硬币的计算必须要么停止翻转并成为一个值（with B），要么翻转硬币并继续（with C），如果硬币出现Heads，另一种方式，如果Tails。抛硬币并告诉你发生了什么的一元操作是

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

现在可以将>>=ofA视为排序掷硬币计算，允许后续计算的选择取决于早期计算提供的值。

如果你有无限的硬币流，那么（除了你非凡的好运之外）你也很幸运能够运行任何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没有非递归参数和两个子树，所以我可以说必须只有一个操作并且它必须只有两个可能的结果，因此掷硬币。

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

于 2012-10-14T17:40:49.230 回答
7

一个好的经验法则return是让它成为最简单可行的东西（当然，任何满足单子定律的定义都可以，但通常你想要结构最小的东西）。在这种情况下，它就像return = B（现在写一个(>>=)匹配！）一样简单。

顺便说一句，这是一个免费的 monad的例子——事实上，它是文档中给出的例子，所以我会让文档自己说话。

于 2012-10-14T17:32:58.230 回答