Skip to content

Instantly share code, notes, and snippets.

@dtipson
Last active November 9, 2021 14:41
  • Star 3 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save dtipson/1637c8ceffd8dbce9c8b7765d864b392 to your computer and use it in GitHub Desktop.
Using a comonad(ish) pattern to create cellular automata in a more functional way. Inspired by this episode of funfunfunction: https://www.youtube.com/watch?v=bc-fVdbjAwk
/*
Native Arrays are not great structures for cellular automata.
Non-empty, circular, doubly-linked lists would be ideal...
but all we really need to do is write a comonadic-like interface
such that it _pretends_ that the array is circular, and can thus
pass the exfn below a sort of "local" slice of an Array as if it were circular.
So you can mostly ignore the implementation mess below
*/
Array.prototype.extendNear = function(exfn){
const len = this.length;
return this.map((_, i ,arr) => {
const nearBy = arr.slice(Math.max(i-1,0),i+2);
if(i===0){
nearBy.unshift(arr[len-1]);
}
if(len===1 || i+1===len){
nearBy.push(arr[0]);
}
return exfn(nearBy);
});
};
/*
Yeah, I modified the native Array type. It's fine. Fight me.
Like I said: with a better-suited type, that function would be MUCH simpler.
Anyhow, now we have a method that can "map" over each element in the array, but instead of passing the value
to the transforming function, it passes an array with the "nearby" values on
either "side." So, we get 3 values for every value, no matter what length the Array is!
We can see what values the exfn is getting for each value in various arrays by using x=>x
*/
[1].extendNear(x=>x);//-> [1,1,1],
[1,2].extendNear(x=>x);//-> -> [[2,1,2], [1,2,1]]
[1,2,3].extendNear(x=>x);//-> [[3,1,2], [1,2,3], [2,3,1]]
/*
However, the normal purpose of .extend is to use those values to generate a _single_
value, born out of its "context." For celluar automata, that means seeing if the context
of any given cell passes a particular set of rules, which determines if it is on or off
in the next generation.
*/
//So next let's look at what a simple CA ruleset looks like:
const ruleSet193 = [
[1, 1, 1],//prevOn, currentlyOn, nextOn
[1, 1, 0],//prevOn, currentlyOn, nextOff
[0, 0, 0] //prevOff, currentlyOff, nextOff
];
/*
Note: this is just the list of rules that would turn a cell "on" because the
"off" rules are implied (it's whatever patterns DON'T match these).
So, if our rulesets are an array of arrays of 3 booleans each, and .extendNear passes exactly such a list...
all we need now is a simple way to compare two arrays of boolean patterns!
That is, each of the rules for turning a cell "on" will be an array, and each "nearby" array
for each value will be an array, so seeing if a rule matches a given "nearby" array is pure "All must match" matching.
I propose this solution, in curried form:
*/
const booleanEquals = arr => arr2 => {
return arr.reduce((acc, x, i)=> acc && x===arr2[i], true);
};
/*
We're going to have a an Array of many different "true" rules for any given ruleset that
we'll want to apply to each sample.
So if we rules.map(booleanEquals(sample)) we'll get an Array of passes/fails we need to boil down into true/false
Since ANY rules passing equates to true, we just reduce this list down into a single value
We could use a monoid structure (Any & mconcat) to do this, but we'll just do it manaually
*/
const anyReducer = (acc, x) => x || acc;//the empty/default acc will be "false"
//now we can write a function that compares any local sample to an entire ruleset!
//if all the above seems way complex/confusing, this function is where all that setup
//pays off. It helps that the above setup is pretty generic/utility stuff rather than super-specific
const anyMatch = ruleset => sample =>
ruleset
.map(booleanEquals(sample))
.reduce(anyReducer, false) ? 1 : 0;
//Now let's create some CA! Here's a way to make a random 1|0 array to start with:
const testArrMaker = length => Array.from(
window.crypto.getRandomValues(new Int8Array(length)).map(x=>x>=0?1:0)
);
//We just create our seed Array of 68 random 1s and 0s...
const testArray = testArrMaker(68);
/*
...and now all we have left to do is:
1) pass a ruleset into anyMatch to generate a matching function for that ruleset
2) pass that matching function into .extendNear
*/
testArray.extendNear(anyMatch(ruleSet193));//-> [1,0,1,1,0,0,1...]
/*
The result is the next generation for a given random array and a given ruleset!
We've abstracted out all the cloning, for-looping, extra temporary value assignment, etc.
We can do it twice to get two generations deep if we feel like:
*/
testArray.extendNear(anyMatch(ruleSet193)).extendNear(anyMatch(ruleSet193));
//And now that we have a FP way to do this to any Array, writing a print loop for multiple generations is pretty trivial.
//Check out: https://goo.gl/DdKYZL or https://tinyurl.com/yhdztf77
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment