StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Hm. I can't help but think this exercise is a little bit unfair as presented.</p> <blockquote> <h3><em>Exercise 4 (the colist Monad)</em></h3> <p>Although <code>repeat</code> and <code>zapp</code> are not the <code>return</code> and <code>ap</code> of the usual <code>Monad []</code> instance, they are none the less the <code>return</code> and <code>ap</code> of an alternative monad, more suited to the coinductive interpretation of <code>[]</code>. What is the <code>join :: [[x]] → [x]</code> of this monad?</p> <p>Comment on the relative efficiency of this monad’s <code>ap</code> and our <code>zapp</code>.</p> </blockquote> <p>First, I'm fairly certain that the monad instance in question is <strong>not valid for <code>[]</code> in general</strong>. When they say "the coinductive interpretation", I suspect this refers to <em>infinite lists</em>. The instance is actually valid for finite lists in certain cases, but not for arbitrary lists in general.</p> <p>So that's your first, very general, hint--why would a monad instance only be valid for certain lists, particularly infinite ones?</p> <p>Here's your second hint: <code>fmap</code> and <code>return</code> are trivial given other definitions earlier in the paper. You already have <code>return</code>; <code>fmap</code> is only slightly less obvious.</p> <p>Furthermore, <code>(>>=)</code> has an easy implementation in terms of the other functions, as with any <code>Monad</code>, which leaves <code>join</code> as the crux of the matter. In most cases <code>(>>=)</code> is more natural for programming with, but <code>join</code> is more conceptually fundamental and in this case, I think, more straightforward to analyze. So I recommend working on that, and forgetting about <code>(>>=)</code> for now. Once you have an implementation, you can go back and reconstruct <code>(>>=)</code> and check the monad laws to make sure it all works properly.</p> <p>Finally, suppose for a moment that you have <code>fmap</code> available, but nothing else. Given values with type <code>[a -> b]</code> and <code>[a]</code>, you can combine them to get something of type <code>[[b]]</code>. The type of <code>join</code> here is <code>[[a]] -> [a]</code>. How might you write <code>join</code> such that you get the same result here that you would from using <code>zapp</code> on the original values? Note that the question about relative efficiency is, as well as a question, a clue about the implementation.</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