Cellular Automata Pair Programming
Mattias Petter Johansson
141

This episode came out literally right on the week I finally convinced myself that I understood, to some degree, comonads.

…which I’m pretty sure would be exactly the FP pattern that could bring more order to operations like this, where the calculation of each cell requires not its own value, but a way to use its entire surrounding context into a new value (which is then recomposed into the entire structure). Functors, Monads, and Comonads all basically allow for the usage of different type-signatures of functions on a given type:

Functor: (a → b) (value to new value)

Monad: (a → M b) (value to a value(s) inside a type)

Comonad: (W b → a) (an entire type with value(s) inside to a value)

Each of these operations starts with and returns the same “type” (an Array and a Promise are the types most people know in javascript) but with different value(s) inside.

In the last case, though, W b represents ALL of the contextual information available on the type, which is then used somehow to calculate a bare value, which is then put back into the type according to its rules.

It’s easiest to think of how those “rules” play out in terms of exactly the case dealt with in the episode: a list of things (and, specifically, a doubly linked, non-empty list), where that transformation is run on every element.

The comonadic pattern, unlike the Functor (transform all the values in this list to a new list with new values) and Monadic one (transform all the values in the list into new lists of values, which are then flattened into a single list), might not seem that interesting at first, until you realize that the W b (in the case of an array, the entire array) is not really the exact same thing for every iterated element: it’s the “entire” type (the entire array)… but usually “seen” from the “perspective” of that element. For simple native Arrays, that normally isn’t defined or that interesting, and at most could potentially mean “an Array of the current element and every remaining element” (so that the transforming function would get fewer and fewer items each time as if work through the list).

But if the Array was instead defined as/conceived of as a circular linked list, or circular array, then what each transform would receive is the entire array… but “focused” on the each element in turn.

That is, if the Array were [1, 2, 3, 4, 5], then for Array.extend(fn) the fn would get [←4, 5, (1), 2, 3→] then [←5, 1, (2), 3, 4→] then [←1, 2, (3), 4, 5→] then [←2, 3,(4), 5, 1→] then [←3, 4, (5), 1, 2→] and it would return each transformed value (just one value) and the result would be a new (circular) Array of the transformed values.

That means that in calculating the new value for each element, we can generalize: speaking in terms of just the “current” element and then those on the left and right of it, applying the exact same rules each time. Because extend takes care of shifting the “focus” as it works through the list, we’re NOT getting the same result each time. That means our functions don’t have to do things like have an incrementing index or anything complex like that to keep track of the “current” element. It’s just something like:

This then allows you to abstract out/generalize a particular set of extending/generation-generating rules to apply to an entire array… without nested for loops or lots of extra variable assignment. The transformation function is thus much simpler and can express the essential idea of the rules/transformation much more clearly.

If that stab at explaining things still isn’t good enough, here’s a quick example of cellular automata dealt with using a comonadic pattern:

Gist walkthrough: https://gist.github.com/dtipson/1637c8ceffd8dbce9c8b7765d864b392

REPL of the pattern in action: https://goo.gl/xJsGw5

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.