StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POhelp on writing "the colist Monad" (Exercise from an Idioms intro paper)
text
Body
copied!<p>I'm reading Conor McBride and Ross Paterson's "Functional Pearl / Idioms: applicative programming with effects:" (The <strike>new</strike> 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 <code>fmap</code> and <code>join</code> or <code>return</code> and <code>>>=</code>?).</p> <h3>Problem Statement</h3> <p>You want to create an <code>instance Monad []</code> where</p> <pre><code>return x = repeat x </code></pre> <p>and <code>ap = zapp</code>.</p> <h3>Standard library functions</h3> <p>As on p. 2 of the paper, <code>ap</code> applies a monadic function-value to a monadic value.</p> <pre><code>ap :: Monad m => m (s -> t) -> m s -> m t ap mf ms = do f <- mf s <- ms return (f s) </code></pre> <p>I expanded this in canonical notation to,</p> <pre><code>ap mf ms = mf >>= (\f -> (ms >>= \s -> return (f s))) </code></pre> <p>The list-specific function <code>zapp</code> ("zippy application") applies a function from one list to a corresponding value in another, namely,</p> <pre><code>zapp (f:fs) (s:ss) = f s : zapp fs ss </code></pre> <h3>My difficulties</h3> <p>Note that in the expanded form, <code>mf :: m (a -> b)</code> is a list of functions <code>[(a -> b)]</code> in our case. So, in the first application of <code>>>=</code>, we have</p> <pre><code>(f:fs) >>= mu </code></pre> <p>where <code>mu = (\f -> (ms >>= \s -> return (f s)))</code>. Now, we can call <code>fs >>= mu</code> as a subroutine, but this doesn't know to remove the first element of <code>ms</code>. (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.</p> <p>Thanks in advance!</p> <h3>Edit 1</h3> <p>I think I got it to work; first I rewrote <code>ap</code> with <code>fmap</code> and <code>join</code> as user "comonad" suggested .</p> <p>My leap of faith was assuming that <code>fmap = map</code>. If anyone can explain how to get there, I'd appreciate it very much. After this, it's clear that <code>join</code> works on the list of lists user "comonad" suggested, and should be the diagonal, <code>\x -> zipWith ((!!) . unL) x [0..]</code>. My complete code is this:</p> <pre><code>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) </code></pre> <p>hopefully that's right (seems to be the "solution" on p. 18 of the paper) ... thanks for the help, everyone!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload