6

Data.Stream のモナド インスタンスは次のように定義されます。

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、最初のストリームの最初の要素、2 番目のストリームの 2 番目の要素などを取得するため、結果のストリームは「主対角線」と見なされ、他のすべての要素が破棄されます。

現在、Georg Cantor が自然数と同じ数の有理数が存在することを証明するために発見した、無限の 2 次元テーブルを通過する方法があります: http://www.jcu.edu/math/vignettes/infinity.htm

ここで私の質問は、joinすべての二次対角線に沿ったパスを使用する (すべてのストリームのすべての要素を訪問する) ことも有効な実装になるかどうかです。それとも、これはモナドの法則の 1 つに違反しますか?

4

2 に答える 2

9

違反だろう

return x >>= f === f x

検討

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

これで、すべての要素を通過した場合、結果の で、要素fmap f (return 1)が繰り返されます。repeat (f 1)joinStream

2次元テーブルとして、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

最近、リストモナドに次のようなものを実装しました。

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)
)

2 番目の項目が 1 以上で、3 番目の項目が 2 以上であるすべての自然数トリプルの無限リストが得られます。

私がチェックしたところ、間違いがなければ、すべてのモナド法則に従うはずです。また、完全に空の対角線に遭遇した後、新しいアイテムを見つけようとするのをやめる有限リストでも機能します。

私はストリーム モナドに詳​​しくないので、そこで同じようなことをしたらどうなるかわかりません。

于 2012-07-27T09:28:05.293 に答える