Skip to content

Instantly share code, notes, and snippets.

@raganwald
Last active December 17, 2022 15:42
Show Gist options
  • Save raganwald/373af7dfbcc43862b088094af2cbbc7f to your computer and use it in GitHub Desktop.
Save raganwald/373af7dfbcc43862b088094af2cbbc7f to your computer and use it in GitHub Desktop.
//
// http://raganwald.com/2019/01/14/structural-sharing-and-copy-on-write.html
// http://raganwald.com/2019/01/26/reduce-reuse-recycle.html
//
const SliceHandler = {
has (slice, property) {
if (property in slice) {
return true;
}
if (typeof property === 'symbol') {
return false;
}
const matchInt = property.match(/^\d+$/);
if (matchInt != null) {
const i = parseInt(property);
return slice.has(i);
}
const matchCarCdr = property.match(/^c([ad]+)r$/);
if (matchCarCdr != null) {
return true;
}
},
get (slice, property) {
if (property in slice) {
return slice[property];
}
if (typeof property === 'symbol') {
return;
}
const matchInt = property.match(/^\d+$/);
if (matchInt != null) {
const i = parseInt(property);
return slice.at(i);
}
const matchCarCdr = property.match(/^c([ad]+)r$/);
if (matchCarCdr != null) {
const [, accessorString] = matchCarCdr;
const accessors = accessorString.split('').map(ad => `c${ad}r`);
return accessors.reduceRight(
(value, accessor) => Slice.of(value)[accessor],
slice);
}
},
set (slice, property, value) {
if (typeof property === 'string') {
const matchInt = property.match(/^\d+$/);
if (matchInt != null) {
const i = parseInt(property);
return slice.atPut(i, value);
}
}
return slice[property] = value;
}
};
function normalizedFrom(arrayIsh, from = 0) {
if (from < 0) {
from = from + arrayIsh.length;
}
from = Math.max(from, 0);
from = Math.min(from, arrayIsh.length);
return from;
}
function normalizedLength(arrayIsh, from, length = arrayIsh.length) {
from = normalizedFrom(arrayIsh, from);
length = Math.max(length, 0);
length = Math.min(length, arrayIsh.length - from);
return length;
}
function normalizedTo(arrayIsh, from, to) {
from = normalizedFrom(arrayIsh, from);
to = Math.max(to, 0);
to = Math.min(arrayIsh.length, to);
return to;
}
const arraySymbol = Symbol('array');
class Slice {
static given(object, from = 0, to = Infinity) {
if (object instanceof this) {
from = normalizedFrom(object, from);
to = normalizedTo(object, from, to);
object.from = object.from + from;
object.length = to - from;
return object;
}
if (object instanceof Array) {
const safe = true;
from = normalizedFrom(object, from);
to = normalizedTo(object, from, to);
return new this(object, from, to - from, safe);
}
if (typeof object[Symbol.iterator] === 'function') {
return this.given([...object], from, to);
}
}
static of(object, from = 0, to = Infinity) {
if (object instanceof this) {
const safe = false;
from = normalizedFrom(object, from);
to = normalizedTo(object, from, to);
return new Slice(object.array, object.from + from, to - from, safe);
}
if (object instanceof Array) {
const safe = false;
from = normalizedFrom(object, from);
to = normalizedTo(object, from, to);
return new this(object, from, to - from, safe);
}
if (typeof object[Symbol.iterator] === 'function') {
return this.given([...object], from, to);
}
}
constructor(array, from, length, safe = false) {
this[arraySymbol] = array;
this.from = normalizedFrom(array, from);
this.length = normalizedLength(array, from, length);
this.safe = safe;
return new Proxy(this, SliceHandler);
}
makeUnsafe () {
this.safe = false;
}
makeSafe () {
const { [arraySymbol]: array, from, length, safe } = this;
if (!safe) {
this[arraySymbol] = array.slice(from, length);
this.from = 0;
this.length = this[arraySymbol].length;
this.safe = true;
}
}
* [Symbol.iterator]() {
const { [arraySymbol]: array, from, length } = this;
for (let i = 0; i < length; i++) {
yield array[i + from];
}
}
join(separator = ",") {
const { [arraySymbol]: array, from, length } = this;
if (length === 0) {
return '';
} else {
let joined = array[from];
for (let i = 1; i < this.length; ++i) {
joined = joined + separator + array[from + i];
}
return joined;
}
}
toString() {
return this.join();
}
slice (from, to = Infinity) {
this.makeUnsafe();
from = normalizedFrom(this, from);
to = normalizedTo(this, from, to);
return Slice.of(this.array, this.from + from, this.from + to);
}
has(i) {
const { [arraySymbol]: array, from, length } = this;
if (i >= 0 && i < length) {
return (from + i) in array;
} else {
return false;
}
}
at(i) {
const { [arraySymbol]: array, from, length } = this;
if (i >= 0 && i < length) {
return array[from + i];
}
}
concat(...args) {
const { [arraySymbol]: array, from, length } = this;
return Slice.of(array.slice(from, length).concat(...args));
}
get [Symbol.isConcatSpreadable]() {
return true;
}
get array() {
this.makeUnsafe();
return this[arraySymbol];
}
atPut (i, value) {
this.makeSafe();
const { [arraySymbol]: array, from, length } = this;
this[arraySymbol] = array.slice(from, length);
this.from = 0;
this.length = this[arraySymbol].length;
return this[arraySymbol][i] = value;
}
push(element) {
this.makeSafe();
const value = this[arraySymbol].push(element);
this.length = this[arraySymbol].length;
return value;
}
pop() {
this.makeSafe();
const value = this[arraySymbol].pop();
this.length = this[arraySymbol].length;
return value;
}
unshift(element) {
this.makeSafe();
const value = this[arraySymbol].unshift(element);
this.length = this[arraySymbol].length;
return value;
}
shift() {
this.makeSafe();
const value = this[arraySymbol].shift();
this.length = this[arraySymbol].length;
return value;
}
}
console.log("==========");
const a1to5 = [1, 2, 3, 4, 5];
const fromZero = new Slice(a1to5, 0);
const fromOne = fromZero.slice(1);
const twoToFour = fromZero.slice(2, 4);
console.log([...fromOne])
console.log([...twoToFour])
console.log(twoToFour[1])
const fromTwo = new Slice(a1to5, 2);
console.log(fromTwo.toString())
console.log([...fromTwo])
//=> [3, 4, 5]
console.log('..........');
function sum (array) {
return sumOfSlice(Slice.of(array), 0);
function sumOfSlice (remaining, runningTotal) {
if (remaining.length === 0) {
return runningTotal;
} else {
const first = remaining[0];
const rest = remaining.slice(1);
return sumOfSlice(rest, runningTotal + first);
}
}
}
const oneToSix = [1, 2, 3, 4, 5, 6];
console.log(sum(oneToSix));
console.log('..........');
const abc = ['a', 'b', 'c'];
const oneTwoThree = Slice.of([1, 2, 3]);
console.log(abc.concat(oneTwoThree))
//=> ["a", "b", "c", 1, 2, 3]
console.log(oneTwoThree.concat(abc).toString())
console.log('..........');
let abasement = ['a', 'b', 'a', 's', 'e', 'm', 'e', 'n', 't'];
let bade = abasement.slice(1, 5);
bade[2] = 'd';
console.log(bade.join(''));
//=> "bade"
let bad = bade.slice(0, 3);
console.log(bad.join(''));
//=> "bad"
let slice = Slice.of(abasement, 1, 5);
slice[2] = 'd';
console.log(slice.join(''));
//=> "bade"
console.log('..........');
const oneToFive = Slice.of([1, 2, 3, 4, 5]);
oneToFive[0] = 'uno';
oneToFive[1] = "zwei";
oneToFive[2] = 'three';
const fourAndFive = oneToFive.slice(3);
oneToFive[3] = 'for';
oneToFive[4] = 'marun';
console.log([...oneToFive]);
//=> ['uno', "zwei", 'three', 'for', 'marun']
console.log([...fourAndFive]);
console.log('..........');
function * countTo (n) {
let i = 1;
while (i <= n) {
yield i++;
}
}
const arrayToTen = Slice.given([...countTo(10)]);
const oneToTen = Slice.given(countTo(10));
console.log(arrayToTen.safe);
console.log(oneToTen.safe);
console.log('..........');
const unsafeTen = Slice.of([...countTo(10)]);
const safeTen = Slice.given([...countTo(10)]);
console.log(unsafeTen.safe);
//=> false
console.log(safeTen.safe);
//=> true
const givenUnsafeTen = Slice.given(unsafeTen);
const givenSafeTen = Slice.given(safeTen);
console.log(givenUnsafeTen.safe);
//=> false
console.log(givenSafeTen.safe);
//=> true
console.log(givenUnsafeTen === unsafeTen);
console.log(givenSafeTen === safeTen);
console.log('..........');
function sum (array) {
return sumOfSlice(Slice.of(array), 0);
function sumOfSlice (remaining, runningTotal) {
if (remaining.length === 0) {
return runningTotal;
} else {
const first = remaining[0];
const rest = Slice.given(remaining, 1);
return sumOfSlice(rest, runningTotal + first);
}
}
}
const oneToSeven = [1, 2, 3, 4, 5, 6, 7];
console.log(sum(oneToSeven));
@ashok-khanna
Copy link

Simply Amazing! Thank you

@raganwald
Copy link
Author

Simply Amazing! Thank you

You are very welcome. I hope you enjoyed the associated blog posts:

  1. Exploring Structural Sharing and Copy-on-Write Semantics, Part I
  2. Structural Sharing and Copy-on-Write Semantics, Part II: Reduce-Reuse-Recycle

@ashok-khanna
Copy link

Simply Amazing! Thank you

You are very welcome. I hope you enjoyed the associated blog posts:

  1. Exploring Structural Sharing and Copy-on-Write Semantics, Part I
  2. Structural Sharing and Copy-on-Write Semantics, Part II: Reduce-Reuse-Recycle

Yes they were great, need a few hours more to fully digest them. I hope to try out your book as well sometime as I write more functional JS code (finding it helps a lot more when dealing with server-client interactions). Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment