Help in writing "colist Monad" (an exercise from the opening article with idioms)

Question

I read Conor McBride and Ross Paterson "Functional Pearl / Idioms: Applied Programming with Effects:" ( new version with "idioms" in the title). I have a little difficulty with exercise 4, as explained below. Any hints would be much appreciated (especially: should I start writing fmap and join or return and >>= ?).

Problem Statement

You want to create instance Monad [] , where

 return x = repeat x 

and ap = zapp .

Standard library functions

As on page 2, ap applies the monadic value of the function to the monadic value.

 ap :: Monad m => m (s -> t) -> ms -> mt ap mf ms = do f <- mf s <- ms return (fs) 

I expanded it in canonical notation,

 ap mf ms = mf >>= (\f -> (ms >>= \s -> return (fs))) 

The list function zapp ("zippy application") applies a function from one list to the corresponding value in another, namely

 zapp (f:fs) (s:ss) = fs : zapp fs ss 

My difficulties

Please note that in expanded form mf :: m (a -> b) is a list of functions [(a -> b)] in our case. So, in the first application >>= we have

 (f:fs) >>= mu 

where mu = (\f -> (ms >>= \s -> return (fs))) . Now we can call fs >>= mu as a subroutine, but it does not know to remove the first ms element. (recall that we want the resulting list to be [f1 s1, f2 s2, ...]. I tried to hack something, but ... as predicted, this did not work ... any help would be greatly appreciated .

Thanks in advance!

Change 1

I think I got him to work; I first rewrote ap with fmap and join , as the user "comonad" suggested.

My leap of faith assumed fmap = map . If anyone can explain how to get there, I would really appreciate it. After this, it is clear that join works in the list of lists that the user "comonad" suggested, and should be a diagonal, \x -> zipWith ((!!) . unL) x [0..] . My full code is:

 newtype L a = L [a] deriving (Eq, Show, Ord) unL (L lst) = lst liftL :: ([a] -> [b]) -> L a -> L b liftL f = L . f . unL joinL :: L (L a) -> L a joinL = liftL $ \x -> zipWith ((!!) . unL) x [0..] instance Functor L where fmap f = liftL (map f) instance Monad L where return x = L $ repeat x m >>= g = joinL (fmap gm) 

I hope this is correct (it seems the “solution” on page 18 of the article) ... thanks for the help, everyone!

Answer 1

Hm. I cannot help but think that this exercise is a little unfair, as presented.

Exercise 4 (Monist Colist)

Although repeat and zapp are not return and ap regular instance of Monad [] they are nonetheless return and ap an alternative monad, more suitable for coinductive interpretation of [] . What is join :: [[x]] → [x] this monad?

Please comment on the relative effectiveness of these ap monads and our zapp .

Firstly, I’m pretty sure that the monad in question is not valid for [] in general . When they say “co-inductive interpretation,” I suspect this refers to endless lists. The instance is valid for leaf lists in some cases, but not for arbitrary lists in general.

So, to your first, very general hint - why was a monad instance valid only for certain lists, especially for endless ones?

Here's your second hint: fmap and return trivial, given other definitions earlier in the document. You already have return ; fmap just a little less obvious.

In addition, (>>=) has an easy implementation in terms of other functions, as with any Monad , which leaves join as the essence of the matter. In most cases (>>=) more natural for programming with, but join more conceptually fundamental and in this case, I think, is easier to analyze. Therefore, I recommend working on it and forgetting about (>>=) . When you have an implementation, you can go back and restore (>>=) and check the laws of the monad to make sure everything is working correctly.

Finally, suppose you have fmap , but nothing else. Given values ​​of type [a -> b] and [a] , you can combine them to get something like [[b]] . The join type is here [[a]] -> [a] . How can you write join to get the same result as when using zapp on the original values? Please note that the question of relative performance as well as the question is the key to implementation.

Answer 2

I just thought that I should clarify that the version with exercises and "Idioms" in the title is rather an earlier draft of the article that eventually appeared in JFP. At that time, I mistakenly believed that colists (by which I mean, possibly infinite, perhaps finite lists) were a monad in a way that corresponds to zapp: there is a plausible candidate for joining (mentioned in other answers), but Jeremy Gibbons was kind enough to indicate to us that he did not satisfy the laws of the monad. Counterexamples include dangling lists of lists with different finite lengths. Accordingly, in the JFP article we corrected. (We were very pleased with this because we love finding applicative functors whose (<*>) is not ap monads.)

Mandatory endless lists (i.e. streams), except for dangling cases, do form a monad, whose ap behaves like a zapp. As a hint, note that the flow x is isomorphic to Nat → x.

My apologies for the confusion. Sometimes it is dangerous to leave old, incomplete drafts (full of errors) lying (ha ha) around on the Internet.

Answer 3

The minimum complete Monad definition is either fmap + return + join , or return + (>>=) . You can implement one with the other:

 (>>=) :: Monad m => ma -> (a->mb) -> mb (>>=) ma amb = join $ fmap amb ma fmap :: Monad m => (a->b) -> ma -> mb fmap f ma = ma >>= (return . f) join :: Monad m => m (ma) -> ma join mma = mma >>= id 

The ap implementation can now be rewritten in terms of join and fmap :

 ap :: Monad m => m (a->b) -> ma -> mb ap mf ma = do f <- mf a <- ma return (fa) ap mf ma = do f <- mf fmap f ma ap mf ma = join $ fmap (flip fmap ma) mf 

---

The exercise gives the semantics of fmap and return and ap . The rest will be obvious as soon as you look at one example:

 ap [f1,f2,f3...] [1,2,3...] = join $ fmap (flip fmap [1,2,3...]) [f1,f2,f3...] = join $ [ [(f1 1), f1 2 , f1 3 ...] , [ f2 1 ,(f2 2), f2 3 ...] , [ f3 1 , f3 2 ,(f3 3)...] ... ] = [(f1 1) , (f2 2) , (f3 3) ... ]