Monad Data.Stream instance definition

Question

The Data.Stream monad instance is defined as follows:

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

This means that join takes the first element of the first stream, the second element of the second stream, etc., therefore, the resulting stream can be considered as the "main diagonal", discarding all other elements.

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

Now my question is: if join , using the path along all secondary diagonals (visiting every element of each thread), would also be the correct implementation. Or will it violate one of the laws of the monad?

Answer 1

It will break

 return x >>= f === fx 

Consider

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

Now fmap f (return 1) is repeat (f 1) , and if join passed through all the elements, the elements will be repeated in the resulting Stream element.

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 cross it along 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 recently applied something like this for a monad list:

 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 need to make a little newtype shenanigans, because you cannot declare another instance of Monad [] , but other than that it works fine. Sort of

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

gives you an endless list of all triples of a natural number whose second element is greater than or equal to 1, and the third element is greater than or equal to 2.

I checked, and if I was not mistaken, he must obey all the laws of the monad. It also works for leaf lists, where it will stop trying to find new items after it encounters a completely empty diagonal.

I am not familiar with the stream monad, so I can’t tell you what will happen if you do something like that too.