Haskell monad返回任意数据类型

Question

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

数据类型如下:

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

但是,我不知道如何定义return语句,因为我无法弄清楚何时返回B值以及何时递归返回C.

任何帮助表示赞赏!

Answer 1

Monad为此类型定义实例的一种方法是将其视为免费 monad.实际上,这需要A a一个带有一个二元运算符的语法C,以及a由B构造函数嵌入的类型值表示的变量.这使得return该B构造,嵌入变量和>>=执行subsitution操作.

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中的一种方式),如果硬币过来Heads,另一个如果Tails.翻转硬币的monadic操作告诉你发生了什么

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没有非递归参数和两个子树,所以我可以说它必须只有一个操作,它必须只有两个可能的结果,因此翻转硬币.

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

Answer 2

一个好的经验法则return是使它成为最简单的可行的东西(当然,任何满足monad定律的定义都很好,但通常你想要的是具有最小结构的东西).在这种情况下,它就像return = B(现在写一个(>>=)匹配!)一样简单.

顺便说一句,这是一个免费monad的例子- 事实上,它是文档中给出的例子,所以我会让文档说明一切.