数据PoE a =空|配对a`单子？ [英] Is `data PoE a = Empty | Pair a a` a monad?
问题描述
这个问题来自
这个答案一个适用于应用但不是Monad的函子：
据称，
数据PoE a = Empty | Pair aa派生（Functor，Eq）
不能有monad实例，但我无法看到：
实例适用PoE其中
纯x =对xx
对fg *对x y =对（f x）（g y）
_ * _ =空
实例Monad PoE其中
空>> = _ =空
一对xy>> = f =
的情况（fx，fy） x'_，Pair_y'） - > Pair x'y'
_ - >清空
我认为这是一个monad的真正原因是它同构于可能（配对a）与配对a = P aa 。它们都是monad，都是可穿越的，所以它们的构成也应该形成monad。 哦，我只是发现并不总是。
哪个柜台单子法的例子吗？ （以及如何系统地查找这些内容？）
edit：我没有想到对这个问题感兴趣。现在，如果我接受系统部分的最佳示例或最佳答案，我必须下定决心。
同时，我想要显示加入适用于更简单的 Pair a = P aa ：
P
________ / \ ________
/ \
PP
/ \ / \
1 2 3 4
它始终采用外部路径，产生 P 1 4 ，通常称为矩阵表示中的对角线。对于monad associativy，我需要三个维度，树形可视化效果更好。从chi的回答中，这是加入失败的例子，以及我如何理解它。
Pair
_________ / \ _________
/ \
Pair Pair
/ \ / \
/ \ / \
Pair Empty Empty Pair
/ \ / \
1 2 3 4
现在您执行加入。通过折叠较低级别的fmap，加入加入。从根目录加入 collapse。
显然，它不是monad。 monad加入的法律之一是
加入。加入=加入。 fmap join
因此，根据上面的定律，这两个输出应该是相等的，但它们不是。
$ $ $ $ $ $ $ $主$ :: $ $ $ $ 1 2）Empty）（Pair Empty（Pair 7 8））
print（join。join $ x）
- output：Pair 1 8
print（join .fmap join $ x）
- output：空
问题在于
join x = Pair（Pair 1 2）（Pair 7 8）
fmap join x = Pair Empty Empty
对这些进行额外的加入并不会使它们相等。
如何系统地找到它？
加入。加入的类型为 m（m（m a）） - > m（ma），所以我从一个三重嵌套 Pair -of - Pair 开始> -of - Pair ，使用数字 1..8 。这工作得很好。然后，我尝试在里面插入一些 Empty ，并很快找到了上面的反例。
一个 m（m（m Int））只包含有限数量的整数，而我们只有构造函数 Pair 和空来尝试。
对于这些检查，我发现加入法则比>> = 的关联性更容易测试。
This question comes from this answer in example of a functor that is Applicative but not a Monad: It is claimed that the
data PoE a = Empty | Pair a a deriving (Functor,Eq)
cannot have a monad instance, but I fail to see that with:
instance Applicative PoE where
pure x = Pair x x
Pair f g <*> Pair x y = Pair (f x) (g y)
_ <*> _ = Empty
instance Monad PoE where
Empty >>= _ = Empty
Pair x y >>= f = case (f x, f y) of
(Pair x' _,Pair _ y') -> Pair x' y'
_ -> Empty
The actual reason why I believe this to be a monad is that it is isomorphic to Maybe (Pair a) with Pair a = P a a. They are both monads, both traversables so their composition should form a monad, too. Oh, I just found out not always.
Which counter-example failes which monad law? (and how to find that out systematically?)
edit: I did not expect such an interest in this question. Now I have to make up my mind if I accept the best example or the best answer to the "systematically" part.
Meanwhile, I want to visualize how join works for the simpler Pair a = P a a:
P
________/ \________
/ \
P P
/ \ / \
1 2 3 4
it always take the outer path, yielding P 1 4, more commonly known as a diagonal in a matrix representation. For monad associativy I need three dimensions, a tree visualization works better. Taken from chi's answer, this is the failing example for join, and how I can comprehend it.
Pair
_________/\_________
/ \
Pair Pair
/\ /\
/ \ / \
Pair Empty Empty Pair
/\ /\
1 2 3 4
Now you do the join . fmap join by collapsing the lower levels first, for join . join collapse from the root.
Apparently, it is not a monad. One of the monad "join" laws is
join . join = join . fmap join
Hence, according to the law above, these two outputs should be equal, but they are not.
main :: IO ()
main = do
let x = Pair (Pair (Pair 1 2) Empty) (Pair Empty (Pair 7 8))
print (join . join $ x)
-- output: Pair 1 8
print (join . fmap join $ x)
-- output: Empty
The problem is that
join x = Pair (Pair 1 2) (Pair 7 8)
fmap join x = Pair Empty Empty
Performing an additional join on those does not make them equal.
how to find that out systematically?
join . join has type m (m (m a)) -> m (m a), so I started with a triple-nested Pair-of-Pair-of-Pair, using numbers 1..8. That worked fine. Then, I tried to insert some Empty inside, and quickly found the counterexample above.
This approach was possible since a m (m (m Int)) only contains a finite amount of integers inside, and we only have constructors Pair and Empty to try.
For these checks, I find the join law easier to test than, say, associativity of >>=.
这篇关于数据PoE a =空|配对a`单子？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
