{"action":"opened","issue":{"url":"https://api.github.com/repos/guevara/read-it-later/issues/1640","repository_url":"https://api.github.com/repos/guevara/read-it-later","labels_url":"https://api.github.com/repos/guevara/read-it-later/issues/1640/labels{/name}","comments_url":"https://api.github.com/repos/guevara/read-it-later/issues/1640/comments","events_url":"https://api.github.com/repos/guevara/read-it-later/issues/1640/events","html_url":"https://github.com/guevara/read-it-later/issues/1640","id":386053021,"node_id":"MDU6SXNzdWUzODYwNTMwMjE=","number":1640,"title":"The stream monad","user":{"login":"guevara","id":228309,"node_id":"MDQ6VXNlcjIyODMwOQ==","avatar_url":"https://avatars1.githubusercontent.com/u/228309?v=4","gravatar_id":"","url":"https://api.github.com/users/guevara","html_url":"https://github.com/guevara","followers_url":"https://api.github.com/users/guevara/followers","following_url":"https://api.github.com/users/guevara/following{/other_user}","gists_url":"https://api.github.com/users/guevara/gists{/gist_id}","starred_url":"https://api.github.com/users/guevara/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/guevara/subscriptions","organizations_url":"https://api.github.com/users/guevara/orgs","repos_url":"https://api.github.com/users/guevara/repos","events_url":"https://api.github.com/users/guevara/events{/privacy}","received_events_url":"https://api.github.com/users/guevara/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-11-30T06:17:29Z","updated_at":"2018-11-30T06:17:29Z","closed_at":null,"author_association":"OWNER","body":"The stream monad<br>\n<br>\nhttps://ift.tt/2RoVmeu<br>\n<br>\njeremygibbons<br>\n<br>\n<div>\n<div>\n<p>I read quite a nice problem on <a href=\"http://zenzike.com/posts/2010-10-21-streams-and-monad-laws/\">Nick Wu&rsquo;s blog</a>, which will serve as a fine warm-up exercise. It&rsquo;s about the fact that streams (infinite lists) form a monad, in a different way from lists. Nick shows the &ldquo;right&rdquo; and two &ldquo;wrong&rdquo; definitions of the join or bind operation, distinguishing them on the basis of the monad laws. But I think Nick&rsquo;s proofs are more complicated than they need to be, because he hasn&rsquo;t fully exploited the recursion patterns that underlie his definitions.</p>\n<p>This post will involve some language that we have not yet covered. Fear not! I hope it will be clear from context. But in case it isn&rsquo;t, you might want to take a look at some of the background material (especially the paper <a href=\"http://www.comlab.ox.ac.uk/publications/publication2360-abstract.html\">Calculating Functional Programs</a>).</p>\n<h2>Streams</h2>\n<p>Like Nick, for simplicity we will take the datatype of streams to be a synonym for lists; in all that follows, assume that lists are properly infinite (not finite, or partial).</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathbf%7Btype%7D%5C%3B%5Cmathit%7BStream%7D%5C%2Ca+%3D+%5Ba%5D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\mathbf{type}\\;\\mathit{Stream}\\,a = [a] \" title=\"\\displaystyle \\mathbf{type}\\;\\mathit{Stream}\\,a = [a] \" class=\"latex\"></p>\n</blockquote>\n<p>Streams are naturally a codatatype rather than a datatype: in the category of sets and total functions, they would be represented as a final coalgebra rather than an initial algebra. In Haskell, which is roughly based on the category of CPOs and continuous functions, initial algebras and final coalgebras coincide, so we need not (indeed, we cannot) make the distinction formally. But we can make it informally, by stipulating that the basic pattern of computation for streams is the <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bunfold%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{unfold}}\" title=\"{\\mathit{unfold}}\" class=\"latex\">:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Bl%7D+%5Cmathit%7Bunfold%7D+%3A%3A+%28b+%5Crightarrow+%28a%2Cb%29%29+%5Crightarrow+b+%5Crightarrow+%5Cmathit%7BStream%7D%5C%2Ca+%5C%5C+%5Cmathit%7Bunfold%7D%5C%2Cf%5C%2Cb+%3D+a+%3A+%5Cmathit%7Bunfold%7D%5C%2Cf%5C%2Cb%27+%5Cqquad%5Cmathbf%7Bwhere%7D%5Cqquad+%28a%2Cb%27%29+%3D+f%5C%2Cb+%5Cend%7Barray%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{l} \\mathit{unfold} :: (b \\rightarrow (a,b)) \\rightarrow b \\rightarrow \\mathit{Stream}\\,a \\\\ \\mathit{unfold}\\,f\\,b = a : \\mathit{unfold}\\,f\\,b' \\qquad\\mathbf{where}\\qquad (a,b') = f\\,b \\end{array}\" title=\"\\displaystyle \\begin{array}{l} \\mathit{unfold} :: (b \\rightarrow (a,b)) \\rightarrow b \\rightarrow \\mathit{Stream}\\,a \\\\ \\mathit{unfold}\\,f\\,b = a : \\mathit{unfold}\\,f\\,b' \\qquad\\mathbf{where}\\qquad (a,b') = f\\,b \\end{array}\" class=\"latex\"></p>\n</blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bunfold%7D%5C%2Cf%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{unfold}\\,f}\" title=\"{\\mathit{unfold}\\,f}\" class=\"latex\"> generates a stream from a seed, using the body <img src=\"https://s0.wp.com/latex.php?latex=%7Bf%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{f}\" title=\"{f}\" class=\"latex\"> that transforms a seed <img src=\"https://s0.wp.com/latex.php?latex=%7Bb%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{b}\" title=\"{b}\" class=\"latex\"> into an element <img src=\"https://s0.wp.com/latex.php?latex=%7Ba%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{a}\" title=\"{a}\" class=\"latex\"> and a new seed <img src=\"https://s0.wp.com/latex.php?latex=%7Bb%27%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{b'}\" title=\"{b'}\" class=\"latex\">. For example, the map function for streams uses the input stream as the seed, repeatedly splitting it into its head and tail:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Bl%7D+%5Cmathit%7BmapS%7D+%3A%3A+%28a+%5Crightarrow+b%29+%5Crightarrow+%5Cmathit%7BStream%7D%5C%2Ca+%5Crightarrow+%5Cmathit%7BStream%7D%5C%2Cb+%5C%5C+%5Cmathit%7BmapS%7D%5C%2Cf+%3D+%5Cmathit%7Bunfold%7D%5C%2C%28%5Cmathit%7Bfork%7D%5C%2C%28f+%5Ccdot+%5Cmathit%7Bhead%7D%2C+%5Cmathit%7Btail%7D%29%29+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{l} \\mathit{mapS} :: (a \\rightarrow b) \\rightarrow \\mathit{Stream}\\,a \\rightarrow \\mathit{Stream}\\,b \\\\ \\mathit{mapS}\\,f = \\mathit{unfold}\\,(\\mathit{fork}\\,(f \\cdot \\mathit{head}, \\mathit{tail})) \\end{array} \" title=\"\\displaystyle \\begin{array}{l} \\mathit{mapS} :: (a \\rightarrow b) \\rightarrow \\mathit{Stream}\\,a \\rightarrow \\mathit{Stream}\\,b \\\\ \\mathit{mapS}\\,f = \\mathit{unfold}\\,(\\mathit{fork}\\,(f \\cdot \\mathit{head}, \\mathit{tail})) \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>where <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bfork%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{fork}}\" title=\"{\\mathit{fork}}\" class=\"latex\"> applies two functions to the same argument:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathit%7Bfork%7D%5C%2C%28f%2Cg%29%5C%2Ca+%3D+%28f%5C%2Ca%2C+g%5C%2Ca%29+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\mathit{fork}\\,(f,g)\\,a = (f\\,a, g\\,a) \" title=\"\\displaystyle \\mathit{fork}\\,(f,g)\\,a = (f\\,a, g\\,a) \" class=\"latex\"></p>\n</blockquote>\n<p>The crucial property of <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bunfold%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{unfold}}\" title=\"{\\mathit{unfold}}\" class=\"latex\"> is its <em>universal property</em>, which provides necessary and sufficient conditions for a computation to be expressible as an instance of <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bunfold%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{unfold}}\" title=\"{\\mathit{unfold}}\" class=\"latex\">:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++h+%3D+%5Cmathit%7Bunfold%7D%5C%2Cf+%5CLeftrightarrow+%5Cmathit%7Bout%7D+%5Ccdot+h+%3D+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2Ch%29+%5Ccdot+f+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle h = \\mathit{unfold}\\,f \\Leftrightarrow \\mathit{out} \\cdot h = \\mathit{prod}\\,(\\mathit{id},h) \\cdot f \" title=\"\\displaystyle h = \\mathit{unfold}\\,f \\Leftrightarrow \\mathit{out} \\cdot h = \\mathit{prod}\\,(\\mathit{id},h) \\cdot f \" class=\"latex\"></p>\n</blockquote>\n<p>where <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bout%7D+%3D+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%2Ctail%29%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{out} = \\mathit{fork}\\,(\\mathit{head},tail)}\" title=\"{\\mathit{out} = \\mathit{fork}\\,(\\mathit{head},tail)}\" class=\"latex\"> deconstructs a stream into its head and tail, and</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathit%7Bprod%7D%5C%2C%28f%2Cg%29%5C%2C%28a%2Cb%29+%3D+%28f%5C%2Ca%2C+g%5C%2Cb%29+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\mathit{prod}\\,(f,g)\\,(a,b) = (f\\,a, g\\,b) \" title=\"\\displaystyle \\mathit{prod}\\,(f,g)\\,(a,b) = (f\\,a, g\\,b) \" class=\"latex\"></p>\n</blockquote>\n<p>From the universal property, one can easily (exercise!) prove three simple consequences (we&rsquo;ll call them the &ldquo;identity&rdquo; and two &ldquo;evaluation&rdquo; rules):</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Bl%7D+%5Cmathit%7Bunfold%7D%5C%2C%5Cmathit%7Bout%7D+%3D+%5Cmathit%7Bid%7D+%5C%5C+%5Cmathit%7Bhead%7D+%5Ccdot+%5Cmathit%7Bunfold%7D%5C%2C%28%5Cmathit%7Bfork%7D%5C%2C%28f%2Cg%29%29+%3D+f+%5C%5C+%5Cmathit%7Btail%7D+%5Ccdot+%5Cmathit%7Bunfold%7D%5C%2C%28%5Cmathit%7Bfork%7D%5C%2C%28f%2Cg%29%29+%3D+%5Cmathit%7Bunfold%7D%5C%2C%28%5Cmathit%7Bfork%7D%5C%2C%28f%2Cg%29%29+%5Ccdot+g+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{l} \\mathit{unfold}\\,\\mathit{out} = \\mathit{id} \\\\ \\mathit{head} \\cdot \\mathit{unfold}\\,(\\mathit{fork}\\,(f,g)) = f \\\\ \\mathit{tail} \\cdot \\mathit{unfold}\\,(\\mathit{fork}\\,(f,g)) = \\mathit{unfold}\\,(\\mathit{fork}\\,(f,g)) \\cdot g \\end{array} \" title=\"\\displaystyle \\begin{array}{l} \\mathit{unfold}\\,\\mathit{out} = \\mathit{id} \\\\ \\mathit{head} \\cdot \\mathit{unfold}\\,(\\mathit{fork}\\,(f,g)) = f \\\\ \\mathit{tail} \\cdot \\mathit{unfold}\\,(\\mathit{fork}\\,(f,g)) = \\mathit{unfold}\\,(\\mathit{fork}\\,(f,g)) \\cdot g \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>and the very important <em>fusion law</em>:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathit%7Bunfold%7D%5C%2Cf+%5Ccdot+h+%3D+%5Cmathit%7Bunfold%7D%5C%2Cg+%5CLeftarrow+f+%5Ccdot+h+%3D+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2Ch%29+%5Ccdot+g&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\mathit{unfold}\\,f \\cdot h = \\mathit{unfold}\\,g \\Leftarrow f \\cdot h = \\mathit{prod}\\,(\\mathit{id},h) \\cdot g\" title=\"\\displaystyle \\mathit{unfold}\\,f \\cdot h = \\mathit{unfold}\\,g \\Leftarrow f \\cdot h = \\mathit{prod}\\,(\\mathit{id},h) \\cdot g\" class=\"latex\"></p>\n</blockquote>\n<p>allowing a preceding function <img src=\"https://s0.wp.com/latex.php?latex=%7Bh%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{h}\" title=\"{h}\" class=\"latex\"> to be absorbed into the unfold.</p>\n<h2>Streams as a monad</h2>\n<p>Making streams a monad amounts to defining functions</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Blcl%7D+%5Cmathit%7Breturn%7D+%26%3A%3A%26+a+%5Crightarrow+%5Cmathit%7BStream%7D%5C%2Ca+%5C%5C+%5Cmathit%7Bjoin%7D+%26%3A%3A%26+%5Cmathit%7BStream%7D%5C%2C%28%5Cmathit%7BStream%7D%5C%2Ca%29+%5Crightarrow+%5Cmathit%7BStream%7D%5C%2Ca+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{lcl} \\mathit{return} &amp;::&amp; a \\rightarrow \\mathit{Stream}\\,a \\\\ \\mathit{join} &amp;::&amp; \\mathit{Stream}\\,(\\mathit{Stream}\\,a) \\rightarrow \\mathit{Stream}\\,a \\end{array} \" title=\"\\displaystyle \\begin{array}{lcl} \\mathit{return} &amp;::&amp; a \\rightarrow \\mathit{Stream}\\,a \\\\ \\mathit{join} &amp;::&amp; \\mathit{Stream}\\,(\\mathit{Stream}\\,a) \\rightarrow \\mathit{Stream}\\,a \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>satisfying the monad laws:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Blcl%7D+%5Cmathit%7Bjoin%7D+%5Ccdot+%5Cmathit%7Breturn%7D+%26%3D%26+%5Cmathit%7Bid%7D+%5C%5C+%5Cmathit%7Bjoin%7D+%5Ccdot+%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Breturn%7D+%26%3D%26+%5Cmathit%7Bid%7D+%5C%5C+%5Cmathit%7Bjoin%7D+%5Ccdot+%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bjoin%7D+%26%3D%26+%5Cmathit%7Bjoin%7D+%5Ccdot+%5Cmathit%7Bjoin%7D+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{lcl} \\mathit{join} \\cdot \\mathit{return} &amp;=&amp; \\mathit{id} \\\\ \\mathit{join} \\cdot \\mathit{mapS}\\,\\mathit{return} &amp;=&amp; \\mathit{id} \\\\ \\mathit{join} \\cdot \\mathit{mapS}\\,\\mathit{join} &amp;=&amp; \\mathit{join} \\cdot \\mathit{join} \\end{array} \" title=\"\\displaystyle \\begin{array}{lcl} \\mathit{join} \\cdot \\mathit{return} &amp;=&amp; \\mathit{id} \\\\ \\mathit{join} \\cdot \\mathit{mapS}\\,\\mathit{return} &amp;=&amp; \\mathit{id} \\\\ \\mathit{join} \\cdot \\mathit{mapS}\\,\\mathit{join} &amp;=&amp; \\mathit{join} \\cdot \\mathit{join} \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>Looking at the type, the obvious (indeed, I think the only possible) definition one can give for <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Breturn%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{return}}\" title=\"{\\mathit{return}}\" class=\"latex\"> is <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Breturn%7D+%3D+%5Cmathit%7Brepeat%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{return} = \\mathit{repeat}}\" title=\"{\\mathit{return} = \\mathit{repeat}}\" class=\"latex\"> where</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathit%7Brepeat%7D+%3D+%5Cmathit%7Bunfold%7D%5C%2C%5Cmathit%7Bdouble%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\mathit{repeat} = \\mathit{unfold}\\,\\mathit{double} \" title=\"\\displaystyle \\mathit{repeat} = \\mathit{unfold}\\,\\mathit{double} \" class=\"latex\"></p>\n</blockquote>\n<p>and <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bdouble%7D+%3D+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bid%7D%2C%5Cmathit%7Bid%7D%29%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{double} = \\mathit{fork}\\,(\\mathit{id},\\mathit{id})}\" title=\"{\\mathit{double} = \\mathit{fork}\\,(\\mathit{id},\\mathit{id})}\" class=\"latex\"> makes two copies of its argument. However, there are many type-correct definitions one could give for <img src=\"https://s0.wp.com/latex.php?latex=%7B+%5Cmathit%7Bjoin%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{ \\mathit{join}}\" title=\"{ \\mathit{join}}\" class=\"latex\">, including <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bhead%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{head}}\" title=\"{\\mathit{head}}\" class=\"latex\">, <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bhead%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{mapS}\\,\\mathit{head}}\" title=\"{\\mathit{mapS}\\,\\mathit{head}}\" class=\"latex\">, and <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bdiag%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{diag}}\" title=\"{\\mathit{diag}}\" class=\"latex\">, where</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathit%7Bdiag%7D+%3D+%5Cmathit%7Bunfold%7D%5C%2C%5Cmathit%7Bhhtt%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\mathit{diag} = \\mathit{unfold}\\,\\mathit{hhtt} \" title=\"\\displaystyle \\mathit{diag} = \\mathit{unfold}\\,\\mathit{hhtt} \" class=\"latex\"></p>\n</blockquote>\n<p>and where (for brevity in what follows) we define</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Blcl%7D+%5Cmathit%7Bhhtt%7D+%26%3D%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhh%7D%2C%5Cmathit%7Btt%7D%29+%5C%5C+%5Cmathit%7Bhh%7D+%26%3D%26+%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D+%5C%5C+%5Cmathit%7Btt%7D+%26%3D%26+%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{lcl} \\mathit{hhtt} &amp;=&amp; \\mathit{fork}\\,(\\mathit{hh},\\mathit{tt}) \\\\ \\mathit{hh} &amp;=&amp; \\mathit{head}\\cdot\\mathit{head} \\\\ \\mathit{tt} &amp;=&amp; \\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail} \\end{array} \" title=\"\\displaystyle \\begin{array}{lcl} \\mathit{hhtt} &amp;=&amp; \\mathit{fork}\\,(\\mathit{hh},\\mathit{tt}) \\\\ \\mathit{hh} &amp;=&amp; \\mathit{head}\\cdot\\mathit{head} \\\\ \\mathit{tt} &amp;=&amp; \\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail} \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>Obviously, <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bhead%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{head}}\" title=\"{\\mathit{head}}\" class=\"latex\"> yields the first &ldquo;row&rdquo; of a stream of streams (if one considers it in row-major order), and <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bhead%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{mapS}\\,\\mathit{head}}\" title=\"{\\mathit{mapS}\\,\\mathit{head}}\" class=\"latex\"> yields the first column; as the name suggests, <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bdiag%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{diag}}\" title=\"{\\mathit{diag}}\" class=\"latex\"> yields the leading diagonal. Nick&rsquo;s post demonstrates that the first two, although type-correct, do not satisfy the monad laws. He also provides a proof that the third does, which we turn to next.</p>\n<h2>Checking the monad laws</h2>\n<p>The proofs that <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Brepeat%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{repeat}}\" title=\"{\\mathit{repeat}}\" class=\"latex\"> and <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bdiag%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{diag}}\" title=\"{\\mathit{diag}}\" class=\"latex\"> satisfy the three monad laws are very straightforward, using the universal property of <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bunfold%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{unfold}}\" title=\"{\\mathit{unfold}}\" class=\"latex\"> and its consequences.</p>\n<p>For the first monad law, fusion gives us the condition to check:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Bll%7D+%26+%5Cmathit%7Bdiag%7D%5Ccdot%5Cmathit%7Brepeat%7D+%3D+%5Cmathit%7Bid%7D+%5C%5C+%5CLeftarrow+%26+%5C%5C+%26+%5Cmathit%7Bhhtt%7D%5Ccdot%5Cmathit%7Brepeat%7D+%3D+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2C%5Cmathit%7Brepeat%7D%29%5Ccdot%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%29+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{diag}\\cdot\\mathit{repeat} = \\mathit{id} \\\\ \\Leftarrow &amp; \\\\ &amp; \\mathit{hhtt}\\cdot\\mathit{repeat} = \\mathit{prod}\\,(\\mathit{id},\\mathit{repeat})\\cdot\\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\end{array} \" title=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{diag}\\cdot\\mathit{repeat} = \\mathit{id} \\\\ \\Leftarrow &amp; \\\\ &amp; \\mathit{hhtt}\\cdot\\mathit{repeat} = \\mathit{prod}\\,(\\mathit{id},\\mathit{repeat})\\cdot\\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>Working on the right-hand side, we have:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Bll%7D+%26+%5Cmathit%7Bhhtt%7D%5Ccdot%5Cmathit%7Brepeat%7D+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bdefinition%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhh%7D%2C%5Cmathit%7Btt%7D%29%5Ccdot%5Cmathit%7Brepeat%7D+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bcomposition+distributes+backwards+over+fork%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhh%7D%5Ccdot%5Cmathit%7Brepeat%7D%2C%5Cmathit%7Btt%7D%5Ccdot%5Cmathit%7Brepeat%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bdefinitions%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Brepeat%7D%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7Brepeat%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bevaluation+for%7E%7D+%5Cmathit%7Brepeat%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7Brepeat%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bnaturality%3B+evaluation%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%2C%5Cmathit%7Brepeat%7D%5Ccdot%5Cmathit%7Btail%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bpairs%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2C%5Cmathit%7Brepeat%7D%29+%5Ccdot+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%29+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{hhtt}\\cdot\\mathit{repeat} \\\\ = &amp; \\qquad \\{ \\mbox{definition} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{hh},\\mathit{tt})\\cdot\\mathit{repeat} \\\\ = &amp; \\qquad \\{ \\mbox{composition distributes backwards over fork} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{hh}\\cdot\\mathit{repeat},\\mathit{tt}\\cdot\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{definitions} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{repeat},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{evaluation for~} \\mathit{repeat} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{naturality; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head},\\mathit{repeat}\\cdot\\mathit{tail}) \\\\ = &amp; \\qquad \\{ \\mbox{pairs} \\} \\\\ &amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{repeat}) \\cdot \\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\end{array} \" title=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{hhtt}\\cdot\\mathit{repeat} \\\\ = &amp; \\qquad \\{ \\mbox{definition} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{hh},\\mathit{tt})\\cdot\\mathit{repeat} \\\\ = &amp; \\qquad \\{ \\mbox{composition distributes backwards over fork} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{hh}\\cdot\\mathit{repeat},\\mathit{tt}\\cdot\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{definitions} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{repeat},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{evaluation for~} \\mathit{repeat} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{naturality; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head},\\mathit{repeat}\\cdot\\mathit{tail}) \\\\ = &amp; \\qquad \\{ \\mbox{pairs} \\} \\\\ &amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{repeat}) \\cdot \\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>discharging the proof obligation.</p>\n<p>Similarly, for the second monad law, fusion gives us the condition:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Bll%7D+%26+%5Cmathit%7Bdiag%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D+%3D+%5Cmathit%7Bid%7D+%5C%5C+%5CLeftarrow+%26+%5C%5C+%26+%5Cmathit%7Bhhtt%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D+%3D+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2C%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D%29%5Ccdot%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%29+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{diag}\\cdot\\mathit{mapS}\\,\\mathit{repeat} = \\mathit{id} \\\\ \\Leftarrow &amp; \\\\ &amp; \\mathit{hhtt}\\cdot\\mathit{mapS}\\,\\mathit{repeat} = \\mathit{prod}\\,(\\mathit{id},\\mathit{mapS}\\,\\mathit{repeat})\\cdot\\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\end{array} \" title=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{diag}\\cdot\\mathit{mapS}\\,\\mathit{repeat} = \\mathit{id} \\\\ \\Leftarrow &amp; \\\\ &amp; \\mathit{hhtt}\\cdot\\mathit{mapS}\\,\\mathit{repeat} = \\mathit{prod}\\,(\\mathit{id},\\mathit{mapS}\\,\\mathit{repeat})\\cdot\\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>and working on the right-hand side, in almost exactly the same steps we get:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Bll%7D+%26+%5Cmathit%7Bhhtt%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bdefinition%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhh%7D%2C%5Cmathit%7Btt%7D%29%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bcomposition+distributes+backwards+over+fork%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhh%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D%2C%5Cmathit%7Btt%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bdefinitions%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bnaturality%3B+evaluation%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bnaturality%3B+functors%3B+evaluation%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%2C%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D%5Ccdot%5Cmathit%7Btail%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bpairs%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2C%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D%29+%5Ccdot+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%29+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{hhtt}\\cdot\\mathit{mapS}\\,\\mathit{repeat} \\\\ = &amp; \\qquad \\{ \\mbox{definition} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{hh},\\mathit{tt})\\cdot\\mathit{mapS}\\,\\mathit{repeat} \\\\ = &amp; \\qquad \\{ \\mbox{composition distributes backwards over fork} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{hh}\\cdot\\mathit{mapS}\\,\\mathit{repeat},\\mathit{tt}\\cdot\\mathit{mapS}\\,\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{definitions} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{mapS}\\,\\mathit{repeat},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{naturality; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{naturality; functors; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head},\\mathit{mapS}\\,\\mathit{repeat}\\cdot\\mathit{tail}) \\\\ = &amp; \\qquad \\{ \\mbox{pairs} \\} \\\\ &amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{mapS}\\,\\mathit{repeat}) \\cdot \\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\end{array} \" title=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{hhtt}\\cdot\\mathit{mapS}\\,\\mathit{repeat} \\\\ = &amp; \\qquad \\{ \\mbox{definition} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{hh},\\mathit{tt})\\cdot\\mathit{mapS}\\,\\mathit{repeat} \\\\ = &amp; \\qquad \\{ \\mbox{composition distributes backwards over fork} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{hh}\\cdot\\mathit{mapS}\\,\\mathit{repeat},\\mathit{tt}\\cdot\\mathit{mapS}\\,\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{definitions} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{mapS}\\,\\mathit{repeat},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{naturality; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{repeat}) \\\\ = &amp; \\qquad \\{ \\mbox{naturality; functors; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head},\\mathit{mapS}\\,\\mathit{repeat}\\cdot\\mathit{tail}) \\\\ = &amp; \\qquad \\{ \\mbox{pairs} \\} \\\\ &amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{mapS}\\,\\mathit{repeat}) \\cdot \\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>discharging the obligation.</p>\n<p>What about the third monad law? To apply the universal property (or fusion), we need one side to be expressed as an unfold; but neither side of the equation <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bdiag%7D%5Ccdot%5Cmathit%7Bdiag%7D+%3D+%5Cmathit%7Bdiag%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bdiag%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{diag}\\cdot\\mathit{diag} = \\mathit{diag}\\cdot\\mathit{mapS}\\,\\mathit{diag}}\" title=\"{\\mathit{diag}\\cdot\\mathit{diag} = \\mathit{diag}\\cdot\\mathit{mapS}\\,\\mathit{diag}}\" class=\"latex\"> is in that form. No matter; let us hypothesize that one side&mdash;say, the left&mdash;can be expressed in the form <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bunfold%7D%5C%2Ch%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{unfold}\\,h}\" title=\"{\\mathit{unfold}\\,h}\" class=\"latex\"> for some <img src=\"https://s0.wp.com/latex.php?latex=%7Bh%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{h}\" title=\"{h}\" class=\"latex\">, then calculate a suitable definition for <img src=\"https://s0.wp.com/latex.php?latex=%7Bh%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{h}\" title=\"{h}\" class=\"latex\"> (if one exists). Assuming we succeed, then we can use fusion to check that the other side equals <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bunfold%7D%5C%2Ch%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{unfold}\\,h}\" title=\"{\\mathit{unfold}\\,h}\" class=\"latex\">. (This strategy doesn&rsquo;t work if we can find no such <img src=\"https://s0.wp.com/latex.php?latex=%7Bh%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{h}\" title=\"{h}\" class=\"latex\">!)</p>\n<p>Again, fusion gives us</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathit%7Bdiag%7D%5Ccdot%5Cmathit%7Bdiag%7D+%3D+%5Cmathit%7Bunfold%7D%5C%2Ch+%5CLeftarrow+%5Cmathit%7Bhhtt%7D%5Ccdot%5Cmathit%7Bdiag%7D+%3D+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2C%5Cmathit%7Bdiag%7D%29%5Ccdot+h+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\mathit{diag}\\cdot\\mathit{diag} = \\mathit{unfold}\\,h \\Leftarrow \\mathit{hhtt}\\cdot\\mathit{diag} = \\mathit{prod}\\,(\\mathit{id},\\mathit{diag})\\cdot h \" title=\"\\displaystyle \\mathit{diag}\\cdot\\mathit{diag} = \\mathit{unfold}\\,h \\Leftarrow \\mathit{hhtt}\\cdot\\mathit{diag} = \\mathit{prod}\\,(\\mathit{id},\\mathit{diag})\\cdot h \" class=\"latex\"></p>\n</blockquote>\n<p>so we calculate:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Bll%7D+%26+%5Cmathit%7Bhhtt%7D%5Ccdot%5Cmathit%7Bdiag%7D+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bdefinition%3B+distribution%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bdiag%7D%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7Bdiag%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bevaluation+for%7E%7D+%5Cmathit%7Bdiag%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7Bdiag%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bnaturality%3B+evaluation%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%2C%5Cmathit%7Bdiag%7D%5Ccdot%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%28%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%29%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bpairs%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2C%5Cmathit%7Bdiag%7D%29%5Ccdot%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%28%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%29%29+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{hhtt}\\cdot\\mathit{diag} \\\\ = &amp; \\qquad \\{ \\mbox{definition; distribution} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{diag},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{diag}) \\\\ = &amp; \\qquad \\{ \\mbox{evaluation for~} \\mathit{diag} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{diag}) \\\\ = &amp; \\qquad \\{ \\mbox{naturality; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{diag}\\cdot\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,(\\mathit{mapS}\\,\\mathit{tail})) \\\\ = &amp; \\qquad \\{ \\mbox{pairs} \\} \\\\ &amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{diag})\\cdot\\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,(\\mathit{mapS}\\,\\mathit{tail})) \\end{array} \" title=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{hhtt}\\cdot\\mathit{diag} \\\\ = &amp; \\qquad \\{ \\mbox{definition; distribution} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{diag},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{diag}) \\\\ = &amp; \\qquad \\{ \\mbox{evaluation for~} \\mathit{diag} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{diag}) \\\\ = &amp; \\qquad \\{ \\mbox{naturality; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{diag}\\cdot\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,(\\mathit{mapS}\\,\\mathit{tail})) \\\\ = &amp; \\qquad \\{ \\mbox{pairs} \\} \\\\ &amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{diag})\\cdot\\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,(\\mathit{mapS}\\,\\mathit{tail})) \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>Therefore, letting</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathit%7Bhhhttt%7D+%3D+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%28%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%29%29+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\mathit{hhhttt} = \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,(\\mathit{mapS}\\,\\mathit{tail})) \" title=\"\\displaystyle \\mathit{hhhttt} = \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,(\\mathit{mapS}\\,\\mathit{tail})) \" class=\"latex\"></p>\n</blockquote>\n<p>we have concluded that</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cmathit%7Bdiag%7D%5Ccdot%5Cmathit%7Bdiag%7D+%3D+%5Cmathit%7Bunfold%7D%5C%2C%5Cmathit%7Bhhhttt%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\mathit{diag}\\cdot\\mathit{diag} = \\mathit{unfold}\\,\\mathit{hhhttt} \" title=\"\\displaystyle \\mathit{diag}\\cdot\\mathit{diag} = \\mathit{unfold}\\,\\mathit{hhhttt} \" class=\"latex\"></p>\n</blockquote>\n<p>Now all we have to do is to check that the right-hand side of the third monad law also equals this; fusion gives us the condition</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Bll%7D+%26+%5Cmathit%7Bdiag%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bdiag%7D+%3D+%5Cmathit%7Bunfold%7D%5C%2C%5Cmathit%7Bhhhttt%7D+%5C%5C+%5CLeftarrow+%26+%5C%5C+%26+%5Cmathit%7Bhhtt%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bdiag%7D+%3D+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2C%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bdiag%7D%29%5Ccdot+%5Cmathit%7Bhhhttt%7D+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{diag}\\cdot\\mathit{mapS}\\,\\mathit{diag} = \\mathit{unfold}\\,\\mathit{hhhttt} \\\\ \\Leftarrow &amp; \\\\ &amp; \\mathit{hhtt}\\cdot\\mathit{mapS}\\,\\mathit{diag} = \\mathit{prod}\\,(\\mathit{id},\\mathit{mapS}\\,\\mathit{diag})\\cdot \\mathit{hhhttt} \\end{array} \" title=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{diag}\\cdot\\mathit{mapS}\\,\\mathit{diag} = \\mathit{unfold}\\,\\mathit{hhhttt} \\\\ \\Leftarrow &amp; \\\\ &amp; \\mathit{hhtt}\\cdot\\mathit{mapS}\\,\\mathit{diag} = \\mathit{prod}\\,(\\mathit{id},\\mathit{mapS}\\,\\mathit{diag})\\cdot \\mathit{hhhttt} \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>and we calculate on the right-hand side:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Bll%7D+%26+%5Cmathit%7Bhhtt%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bdiag%7D+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bdefinition%3B+distribution%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bdiag%7D%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bdiag%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bnaturality%3B+evaluation%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bdiag%7D%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bfunctors%3B+naturality%3B+evaluation%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%5Ccdot%5Cmathit%7Bhead%7D%2C%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bdiag%7D%5Ccdot%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%28%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D%29%29+%5C%5C+%3D+%26+%5Cqquad+%5C%7B+%5Cmbox%7Bpairs%3B+definition%7D+%5C%7D+%5C%5C+%26+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2C%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Bdiag%7D%29%5Ccdot%5Cmathit%7Bhhhttt%7D+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{hhtt}\\cdot\\mathit{mapS}\\,\\mathit{diag} \\\\ = &amp; \\qquad \\{ \\mbox{definition; distribution} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{mapS}\\,\\mathit{diag},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{diag}) \\\\ = &amp; \\qquad \\{ \\mbox{naturality; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{diag}) \\\\ = &amp; \\qquad \\{ \\mbox{functors; naturality; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{mapS}\\,\\mathit{diag}\\cdot\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,(\\mathit{mapS}\\,\\mathit{tail})) \\\\ = &amp; \\qquad \\{ \\mbox{pairs; definition} \\} \\\\ &amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{mapS}\\,\\mathit{diag})\\cdot\\mathit{hhhttt} \\end{array} \" title=\"\\displaystyle \\begin{array}{ll} &amp; \\mathit{hhtt}\\cdot\\mathit{mapS}\\,\\mathit{diag} \\\\ = &amp; \\qquad \\{ \\mbox{definition; distribution} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{mapS}\\,\\mathit{diag},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{diag}) \\\\ = &amp; \\qquad \\{ \\mbox{naturality; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{diag}) \\\\ = &amp; \\qquad \\{ \\mbox{functors; naturality; evaluation} \\} \\\\ &amp; \\mathit{fork}\\,(\\mathit{head}\\cdot\\mathit{head}\\cdot\\mathit{head},\\mathit{mapS}\\,\\mathit{diag}\\cdot\\mathit{tail}\\cdot\\mathit{mapS}\\,\\mathit{tail}\\cdot\\mathit{mapS}\\,(\\mathit{mapS}\\,\\mathit{tail})) \\\\ = &amp; \\qquad \\{ \\mbox{pairs; definition} \\} \\\\ &amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{mapS}\\,\\mathit{diag})\\cdot\\mathit{hhhttt} \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>completing the proof.</p>\n<p>As you&rsquo;ll see, the calculations are all quite short and simple, whereas in Nick&rsquo;s formulation, they were rather hard work; I think that was (a) because he wasn&rsquo;t exploiting the universal property, and (b) because he was working in terms of the &ldquo;bind&rdquo; rather than the &ldquo;join&rdquo; of the monad, which forced him into a more pointwise rather than pointfree style. Points are helpful when writing programs, but less so when reasoning about them.</p>\n<h2>Deducing diag</h2>\n<p>Here&rsquo;s another way of looking at the problem. Nick&rsquo;s blog presented three plausible (that is, type-correct) definitions for the <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bjoin%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{join}}\" title=\"{\\mathit{join}}\" class=\"latex\"> operation. Two of these didn&rsquo;t satisfy the necessary laws, so were evidently wrong. The third, <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Bdiag%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{diag}}\" title=\"{\\mathit{diag}}\" class=\"latex\">, does satisfy the laws, but is it the only possible definition that does? I believe that it is the only solution in the form of an unfold; but I only have a hand-waving argument as to why.</p>\n<p>Let us suppose that indeed</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++join+%3D+%5Cmathit%7Bunfold%7D%5C%2Ck+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle join = \\mathit{unfold}\\,k \" title=\"\\displaystyle join = \\mathit{unfold}\\,k \" class=\"latex\"></p>\n</blockquote>\n<p>for some <img src=\"https://s0.wp.com/latex.php?latex=%7Bk%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k}\" title=\"{k}\" class=\"latex\">. Without loss of generality, let us suppose also that</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++k+%3D+%5Cmathit%7Bfork%7D%5C%2C%28k_1%2Ck_2%29+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle k = \\mathit{fork}\\,(k_1,k_2) \" title=\"\\displaystyle k = \\mathit{fork}\\,(k_1,k_2) \" class=\"latex\"></p>\n</blockquote>\n<p>with</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Blcl%7D+k_1+%26%3A%3A%26+%5Cmathit%7BStream%7D%5C%2C%28%5Cmathit%7BStream%7D%5C%2Ca%29+%5Crightarrow+a+%5C%5C+k_2+%26%3A%3A%26+%5Cmathit%7BStream%7D%5C%2C%28%5Cmathit%7BStream%7D%5C%2Ca%29+%5Crightarrow+%5Cmathit%7BStream%7D%5C%2C%28%5Cmathit%7BStream%7D%5C%2Ca%29+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{lcl} k_1 &amp;::&amp; \\mathit{Stream}\\,(\\mathit{Stream}\\,a) \\rightarrow a \\\\ k_2 &amp;::&amp; \\mathit{Stream}\\,(\\mathit{Stream}\\,a) \\rightarrow \\mathit{Stream}\\,(\\mathit{Stream}\\,a) \\end{array} \" title=\"\\displaystyle \\begin{array}{lcl} k_1 &amp;::&amp; \\mathit{Stream}\\,(\\mathit{Stream}\\,a) \\rightarrow a \\\\ k_2 &amp;::&amp; \\mathit{Stream}\\,(\\mathit{Stream}\\,a) \\rightarrow \\mathit{Stream}\\,(\\mathit{Stream}\\,a) \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>I claimed above that <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Brepeat%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{repeat}}\" title=\"{\\mathit{repeat}}\" class=\"latex\"> is the only type-correct definition of the <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Breturn%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{return}}\" title=\"{\\mathit{return}}\" class=\"latex\"> operation. (Ignoring bottoms, that is. Which is to say, in Haskell, all type-correct definitions are approximations in the definedness ordering to <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Brepeat%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{repeat}}\" title=\"{\\mathit{repeat}}\" class=\"latex\">.)</p>\n<p>Consideration of just the first two monad laws gives us some constraints on <img src=\"https://s0.wp.com/latex.php?latex=%7Bk%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k}\" title=\"{k}\" class=\"latex\">, since we know that <img src=\"https://s0.wp.com/latex.php?latex=%7B%5Cmathit%7Breturn%7D+%3D+%5Cmathit%7Brepeat%7D%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{\\mathit{return} = \\mathit{repeat}}\" title=\"{\\mathit{return} = \\mathit{repeat}}\" class=\"latex\">:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Blcl%7D+k%5Ccdot%5Cmathit%7Brepeat%7D+%26%3D%26+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2C%5Cmathit%7Brepeat%7D%29%5Ccdot%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%29+%5C%5C+k%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D+%26%3D%26+%5Cmathit%7Bprod%7D%5C%2C%28%5Cmathit%7Bid%7D%2C%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D%29%5Ccdot%5Cmathit%7Bfork%7D%5C%2C%28%5Cmathit%7Bhead%7D%2C%5Cmathit%7Btail%7D%29+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{lcl} k\\cdot\\mathit{repeat} &amp;=&amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{repeat})\\cdot\\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\\\ k\\cdot\\mathit{mapS}\\,\\mathit{repeat} &amp;=&amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{mapS}\\,\\mathit{repeat})\\cdot\\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\end{array} \" title=\"\\displaystyle \\begin{array}{lcl} k\\cdot\\mathit{repeat} &amp;=&amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{repeat})\\cdot\\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\\\ k\\cdot\\mathit{mapS}\\,\\mathit{repeat} &amp;=&amp; \\mathit{prod}\\,(\\mathit{id},\\mathit{mapS}\\,\\mathit{repeat})\\cdot\\mathit{fork}\\,(\\mathit{head},\\mathit{tail}) \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>Or in terms of <img src=\"https://s0.wp.com/latex.php?latex=%7Bk%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k}\" title=\"{k}\" class=\"latex\">&lsquo;s two components,</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++%5Cbegin%7Barray%7D%7Blcll%7D+k_1%5Ccdot%5Cmathit%7Brepeat%7D+%26%3D%26+%5Cmathit%7Bhead%7D+%26%281%29%5C%5C+k_2%5Ccdot%5Cmathit%7Brepeat%7D+%26%3D%26+%5Cmathit%7Brepeat%7D%5Ccdot%5Cmathit%7Btail%7D+%26%282%29%5C%5C+k_1%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D+%26%3D%26+%5Cmathit%7Bhead%7D+%26%283%29%5C%5C+k_2%5Ccdot%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D+%26%3D%26+%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Brepeat%7D%5Ccdot%5Cmathit%7Btail%7D+%26%284%29+%5Cend%7Barray%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle \\begin{array}{lcll} k_1\\cdot\\mathit{repeat} &amp;=&amp; \\mathit{head} &amp;(1)\\\\ k_2\\cdot\\mathit{repeat} &amp;=&amp; \\mathit{repeat}\\cdot\\mathit{tail} &amp;(2)\\\\ k_1\\cdot\\mathit{mapS}\\,\\mathit{repeat} &amp;=&amp; \\mathit{head} &amp;(3)\\\\ k_2\\cdot\\mathit{mapS}\\,\\mathit{repeat} &amp;=&amp; \\mathit{mapS}\\,\\mathit{repeat}\\cdot\\mathit{tail} &amp;(4) \\end{array} \" title=\"\\displaystyle \\begin{array}{lcll} k_1\\cdot\\mathit{repeat} &amp;=&amp; \\mathit{head} &amp;(1)\\\\ k_2\\cdot\\mathit{repeat} &amp;=&amp; \\mathit{repeat}\\cdot\\mathit{tail} &amp;(2)\\\\ k_1\\cdot\\mathit{mapS}\\,\\mathit{repeat} &amp;=&amp; \\mathit{head} &amp;(3)\\\\ k_2\\cdot\\mathit{mapS}\\,\\mathit{repeat} &amp;=&amp; \\mathit{mapS}\\,\\mathit{repeat}\\cdot\\mathit{tail} &amp;(4) \\end{array} \" class=\"latex\"></p>\n</blockquote>\n<p>I claim that (1) entails that <img src=\"https://s0.wp.com/latex.php?latex=%7Bk_1%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k_1}\" title=\"{k_1}\" class=\"latex\"> picks some element out of the first &ldquo;column&rdquo; of a stream of streams (thinking of the input as an infinite matrix in row-major order again)&mdash;for the equation says that when the input consists of infinitely many copies of the same stream, <img src=\"https://s0.wp.com/latex.php?latex=%7Bk_1%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k_1}\" title=\"{k_1}\" class=\"latex\"> picks (one of the many copies of) the head of that stream. Symmetrically, (3) entails that, when given a infinite matrix whose columns are all equal, <img src=\"https://s0.wp.com/latex.php?latex=%7Bk_1%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k_1}\" title=\"{k_1}\" class=\"latex\"> picks some element out of the first &ldquo;row&rdquo;. And because <img src=\"https://s0.wp.com/latex.php?latex=%7Bk_1%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k_1}\" title=\"{k_1}\" class=\"latex\"> has to be polymorphic, it cannot behave differently on special matrices like these than it does in general. Putting those statements together, and waving my hands in the air, I conclude that <img src=\"https://s0.wp.com/latex.php?latex=%7Bk_1%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k_1}\" title=\"{k_1}\" class=\"latex\"> picks the only element that is in both the first row and the first column:</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++k_1+%3D+%5Cmathit%7Bhead%7D+%5Ccdot+%5Cmathit%7Bhead%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle k_1 = \\mathit{head} \\cdot \\mathit{head} \" title=\"\\displaystyle k_1 = \\mathit{head} \\cdot \\mathit{head} \" class=\"latex\"></p>\n</blockquote>\n<p>Similarly, Equation (2) says that, given an infinite input matrix all of whose rows are equal, <img src=\"https://s0.wp.com/latex.php?latex=%7Bk_2%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k_2}\" title=\"{k_2}\" class=\"latex\"> drops the first column (and possibly some of the rows are duplicated or dropped, and the order of the rows may change; but the elements of the rows are untouched). Symmetrically, (4) says that, given an input whose columns are all equal, <img src=\"https://s0.wp.com/latex.php?latex=%7Bk_2%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k_2}\" title=\"{k_2}\" class=\"latex\"> drops the first row (and may duplicate, drop, or rearrange the columns, but not change any of them). And again, the behaviour in general must be consistent with these special cases. Putting these observations together, <img src=\"https://s0.wp.com/latex.php?latex=%7Bk_2%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k_2}\" title=\"{k_2}\" class=\"latex\"> must drop the first row and the first column, and cannot change any of the remainder of the matrix.</p>\n<blockquote>\n<p><img src=\"https://s0.wp.com/latex.php?latex=%5Cdisplaystyle++k_2+%3D+%5Cmathit%7Btail%7D+%5Ccdot+%5Cmathit%7BmapS%7D%5C%2C%5Cmathit%7Btail%7D+&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"\\displaystyle k_2 = \\mathit{tail} \\cdot \\mathit{mapS}\\,\\mathit{tail} \" title=\"\\displaystyle k_2 = \\mathit{tail} \\cdot \\mathit{mapS}\\,\\mathit{tail} \" class=\"latex\"></p>\n</blockquote>\n<p>What is the right framework in which to present such arguments more formally? It feels rather like Paul Hoogendijk&rsquo;s <a href=\"http://dx.doi.org/10.1017/S0956796899003640\">relational approach to generic programming</a>, which has to talk about largest natural transformations of a given type: the relational setting provides the conjunction one needs in order to express the two separate constraints on <img src=\"https://s0.wp.com/latex.php?latex=%7Bk_1%7D&amp;bg=ffffff&amp;fg=000000&amp;s=0\" alt=\"{k_1}\" title=\"{k_1}\" class=\"latex\">.</p>\n<p id=\"atatags-370373-5c00c80a2afba\"></p>\n</div>\n</div>\n<br>\n<br>\n<br>\n<br>\nFunctional<br>\n<br>\nvia Patterns in Functional Programming https://ift.tt/1of8G6g<br>\n<br>\nDecember 31, 2010 at 06:00PM"}}
{"actor":{"display_login":"guevara"}}