help on writing "the colist Monad" (Exercise from an Idioms intro paper)

I'm reading Conor McBride and Ross Paterson's "Functional Pearl / Idioms: applicative programming with effects:" (The new version, with "idioms" in the title). I'm having a little difficulty with Exercise 4, which is 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 an instance Monad [] where

return x = repeat x

and ap = zapp.

Standard li开发者_运维知识库brary functions

As on p. 2 of the paper, ap applies a monadic function-value to a monadic value.

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

I expanded this in canonical notation to,

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

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

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

My difficulties

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

(f:fs) >>= mu

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

Thanks in advance!

Edit 1

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

My leap of faith was assuming that fmap = map. If anyone can explain how to get there, I'd appreciate it very much. After this, it's clear that join works on the list of lists user "comonad" suggested, and should be the diagonal, \x -> zipWith ((!!) . unL) x [0..]. My complete code is this:

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

hopefully that's right (seems to be the "solution" on p. 18 of the paper) ... thanks for the help, everyone!

---

Hm. I can't help but think this exercise is a little bit unfair as presented.

Exercise 4 (the colist Monad)

Although repeat and zapp are not the return and ap of the usual Monad [] instance, they are none the less the return and ap of an alternative monad, more suited to the coinductive interpretation of []. What is the join :: [[x]] → [x] of this monad?

Comment on the relative efficiency of this monad’s ap and our zapp.

First, I'm fairly certain that the monad instance in question is not valid for [] in general. When they say "the coinductive interpretation", I suspect this refers to infinite lists. The instance is actually valid for finite lists in certain cases, but not for arbitrary lists in general.

So that's your first, very general, hint--why would a monad instance only be valid for certain lists, particularly infinite ones?

Here's your second hint: fmap and return are trivial given other definitions earlier in the paper. You already have return; fmap is only slightly less obvious.

Furthermore, (>>=) has an easy implementation in terms of the other functions, as with any Monad, which leaves join as the crux of the matter. In most cases (>>=) is more natural for programming with, but join is more conceptually fundamental and in this case, I think, more straightforward to analyze. So I recommend working on that, and forgetting about (>>=) for now. Once you have an implementation, you can go back and reconstruct (>>=) and check the monad laws to make sure it all works properly.

Finally, suppose for a moment that you have fmap available, but nothing else. Given values with type [a -> b] and [a], you can combine them to get something of type [[b]]. The type of join here is [[a]] -> [a]. How might you write join such that you get the same result here that you would from using zapp on the original values? Note that the question about relative efficiency is, as well as a question, a clue about the implementation.

---

I just thought I should clarify that the version with exercises and "Idioms" in the title is a rather earlier draft of the paper which eventually appeared in JFP. At that time, I mistakenly thought that colists (by which I mean possibly infinite, possibly finite lists) were a monad in a way which corresponds to zapp: there is a plausible candidate for the join (alluded to in other answers) but Jeremy Gibbons was kind enough to point out to us that it does not satisfy the monad laws. The counterexamples involve "ragged" lists of lists with varying finite lengths. Correspondingly, in the JFP article, we stood corrected. (We were rather happy about it, because we love to find applicative functors whose (<*>) is not the ap of a Monad.)

The necessarily infinite lists (i.e. streams), by ruling out the ragged cases, do indeed form a monad whose ap behaves like zapp. For a clue, note that Stream x is isomorphic to Nat -> x.

My apologies for the confusion. It's sometimes dangerous leaving old, unfinished drafts (replete with errors) lying (ha ha) around on the web.

---

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

(>>=) :: Monad m => m a -> (a->m b) -> m b
(>>=) ma amb = join $ fmap amb ma

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

Now, the implementation of ap can be rewritten in terms of join and fmap:

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

---

In the exercise, the semantics of fmap and return and ap are given. The rest will be obvious, as soon as you examine 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)
                              ...
                              ]