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

Question

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 library 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!

Answer 1

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.