<div dir="ltr"><div class="gmail_default" style="font-family:verdana,sans-serif;font-size:small;color:#333333">(reposted for readability)<br><br>Comonads, like trees or stacks, are data structures which guide a<br>computation along a chosen line and imply a mode of reasoning. That they<br>first arose in the context of category theory should not make them lesser<br>citizens.<br><br>What the comonad captures is the essence of locality[\u25ca], like it&#39;s dual<br>captures the essence of encapsulation. The comonadic cellular automata,<br>assigns to each cell a world with that cell at its center (subjectivity?).<br>That this assignment can be done *naturally* (via the natural lifting<br>\u03b4: W -&gt; W²) and progressed (via the composition W_\u03b2 \u25cb \u03b4) means that one<br>can handle many of the implementation details in the coalgebra, which a<br>language&#39;s compiler can be tuned to exploit. Two points of exploitation<br>that come immediately to mind being:<br><br>1. parallelization (especially wrt adaptive chunking)<br>2. algebrao-functional reduction (I&#39;m not sure what to technically call this)<br><br>Beyond this, I rather like not having to build in the topological<br>constraints in the low level details. Instead, as in my implementation[!],<br>one can allow computation over doubly unbounded lists and lists of lists<br>while only making the judicious choice of board size and it&#39;s accompanying<br>details later. In practice, I like this style of implementation because<br>it generalizes nicely while remaining structured (maintainability) and<br>suggests a clearer perspective from which to understand cellular automata,<br>that of a naturally localized computation.<br><br>The reason I mention this is that the comonadic-style walls-off each cell,<br>in a sense, much like David Lewis&#39; counterparts. To write a shuffle in<br>this style is easy, but I suspect that to purely write a sort this way is<br>impossible. I would love to know whether this is, in fact, true.<br><br>[\u25a1] Yes, I know that his theory is less popular than Kripke&#39;s, but hey.<br><a href="https://en.wikipedia.org/wiki/Counterpart_theory">https://en.wikipedia.org/wiki/Counterpart_theory</a><br><br>[\u25ca] Arguably, this &quot;essence of locality&quot; is an expression of *possible<br>worlds*, via the adjunction: X -&gt; \u25a1Y iff X -&gt; Y, or \u25ca \u22a3 \u25a1. More on this<br>can be read here: <a href="https://ncatlab.org/nlab/show/necessity+and+possibility#:~:text=3.-,Possible%20worlds%20via%20first-order%20logic%20and%20type%20theory,-One%20common%20philosophical">https://ncatlab.org/nlab/show/necessity+and+possibility#:~:text=3.-,Possible%20worlds%20via%20first-order%20logic%20and%20type%20theory,-One%20common%20philosophical</a><br><br>[!] But the original idea here isn&#39;t mine, I followed up on ideas written here: <a href="http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html">http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html</a><br></div></div>