6

Data.Stream 的 monad 实例是这样定义的：

instance Monad Stream where
  return = repeat
  xs >>= f = join (fmap f xs)
    where
      join :: Stream (Stream a) -> Stream a
      join ~(Cons xs xss) = Cons (head xs) (join (map tail xss))

这意味着join采用第一个流的第一个元素，第二个流的第二个元素等，因此结果流可以被视为“主对角线”，丢弃所有其他元素。

现在有一种方法可以通过无限二维表，由 Georg Cantor 发现，他证明有理数与自然数一样多：http ://www.jcu.edu/math/vignettes/infinity.htm

现在我的问题是，如果join使用沿所有次对角线的路径（访问每个流的每个元素）也是有效的实现。或者这会违反单子定律之一吗？

4

2 回答 2

9

会违反

return x >>= f === f x

考虑

f k = Cons k (f (k+1))

现在fmap f (return 1)是repeat (f 1)，如果join遍历所有元素，在结果Stream中，元素会重复。

作为一个二维表，fmap f (return 1)看起来像

1 2 3 4 ...
1 2 3 4 ...
1 2 3 4 ...

如果你沿着次对角线遍历它，你会得到

1 1 2 1 2 3 1 2 3 4 ...

1 2 3 4 5 ...而不是f 1.

于 2012-07-27T09:15:28.447 回答
1

我最近为 list monad 实现了类似的东西：

diagonals :: [[(Integer, Integer)]]
diagonals =
    let diagonal index =
        do
            number <- [0..index]
            return (number, index - number)
    in map diagonal (enumFrom 0)

newtype Enumerable a = Enumerable { list :: [a] }

instance Monad Enumerable where
    return item = Enumerable [item]
    enumerable1 >>= getEnumerable2 =
        let
            list1 = list enumerable1
            diagonalItems diagonal =
                do
                    (index1, index2) <- diagonal
                    guard (containsIndex list1 index1)
                    let item1 = genericIndex list1 index1
                    let list2 = list (getEnumerable2 item1)
                    guard (containsIndex list2 index2)
                    let item2 = genericIndex list2 index2
                    return item2
        in Enumerable (concat (takeWhile (not . null) (map diagonalItems diagonals)))

不幸的是，你必须做一些newtype恶作剧，因为你不能声明另一个实例Monad []，但除此之外，它工作正常。就像是

list
(
    do
        item1 <- Enumerable [0..]
        item2 <- Enumerable [1..]
        item3 <- Enumerable [2..]
        return (item1, item2, item3)
)

为您提供所有自然数三元组的无限列表，其中第二项大于或等于 1，第三项大于或等于 2。

我检查了一下，如果我没有犯错，它应该遵守所有的单子定律。它也适用于有限列表，在遇到完全空的对角线后它将停止尝试查找新项目。

我不熟悉流单子，所以我不能告诉你如果你在那里做类似的事情会发生什么。

于 2012-07-27T09:28:05.293 回答