Definition of the Monad Instance of Data.Stream

Question

The monad instanc of Data.Stream is defined that way:

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

That means join takes the first element of the first stream, the second element of the second stream etc, so the resulting stream can be seen as "main diagonal", discarding all other elements.

Now there is a way to go through an infinite two-dimensional table, discovered by Georg Cantor for his proof that there are as many rational numbers as natural numbers: http://www.jcu.edu/math/vignettes/infinity.htm

Now my question is if a join using a path along all secondary diagonals (visiting every element of every stream) would be a valid implementation as well. Or would this violate one of the monad laws?

Answer 1

It would violate

return x >>= f === f x

Consider

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

Now fmap f (return 1) is repeat (f 1) and if join went through all elements, in the resulting Stream, elements would repeat.

As a two-dimensional table, fmap f (return 1) looks like

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

and if you traverse that following the secondary diagonals, you get

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

and not 1 2 3 4 5 ... as with f 1.

Answer 2

I implemented something like this for the list monad recently:

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

Unfortunately, you have to do a little bit of newtype shenanigans because you can't declare another instance of Monad [], but other than that, it works fine. Something like

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

gives you an infinite list of all the natural number triples whose second item is greater than or equal to 1 and whose third item is greater than or equal to 2.

I checked and if I didn't make a mistake, it should obey all the monad laws. It also works for finite lists, where it will stop trying to find new items after encountering a diagonal that is completely empty.

I'm not familiar with the stream monad, so I can't tell you what would happen if you did something like that there, aswell.