Here is the sequential question after
How to store data of a functional chain of Monoidal List?
and
Extracting data from a function chain without arrays
and here I would like to express my respect and appreciation for contributors to my Questions, especially by @Aadit M Shah and @user633183
Now, this question is opened to clarify the similarities and differences or relation between Difference list and Church list
.
Difference list
https://mcmap.net/q/1781695/-how-to-store-data-of-a-functional-chain-of-monoidal-list
A difference list is a function that takes a list and prepends another list to it. For example:
const concat = xs => ys => xs.concat(ys); // This creates a difference list.
const f = concat([1,2,3]); // This is a difference list.
console.log(f([])); // You can get its value by applying it to the empty array.
console.log(f([4,5,6])); // You can also apply it to any other array.The cool thing about difference lists are that they form a monoid because they are just endofunctions:
const id = x => x; // The identity element is just the id function.
const compose = (f, g) => x => f(g(x)); // The binary operation is composition.
compose(id, f) = f = compose(f, id); // identity law
compose(compose(f, g), h) = compose(f, compose(g, h)); // associativity law
Even better, you can package them into a neat little class where function composition is the dot operator:
class DList {
constructor(f) {
this.f = f;
this.id = this;
}
cons(x) {
return new DList(ys => this.f([x].concat(ys)));
}
concat(xs) {
return new DList(ys => this.f(xs.concat(ys)));
}
apply(xs) {
return this.f(xs);
}
}
const id = new DList(x => x);
const cons = x => new DList(ys => [x].concat(ys)); // Construct DList from value.
const concat = xs => new DList(ys => xs.concat(ys)); // Construct DList from array.
id . concat([1, 2, 3]) = concat([1, 2, 3]) = concat([1, 2, 3]) . id // identity law
concat([1, 2]) . cons(3) = cons(1) . concat([2, 3]) // associativity law
You can use the
applymethod to retrieve the value of theDListas follows:
class DList {
constructor(f) {
this.f = f;
this.id = this;
}
cons(x) {
return new DList(ys => this.f([x].concat(ys)));
}
concat(xs) {
return new DList(ys => this.f(xs.concat(ys)));
}
apply(xs) {
return this.f(xs);
}
}
const id = new DList(x => x);
const cons = x => new DList(ys => [x].concat(ys));
const concat = xs => new DList(ys => xs.concat(ys));
const identityLeft = id . concat([1, 2, 3]);
const identityRight = concat([1, 2, 3]) . id;
const associativityLeft = concat([1, 2]) . cons(3);
const associativityRight = cons(1) . concat([2, 3]);
console.log(identityLeft.apply([])); // [1,2,3]
console.log(identityRight.apply([])); // [1,2,3]
console.log(associativityLeft.apply([])); // [1,2,3]
console.log(associativityRight.apply([])); // [1,2,3]An advantage of using difference lists over regular lists (functional lists, not JavaScript arrays) is that concatenation is more efficient because the lists are concatenated from right to left. Hence, it doesn't copy the same values over and over again if you're concatenating multiple lists.
Church Encoding List
As an alternative to the encoding using Church pairs, a list can be encoded by identifying it with its right fold function. For example, a list of three elements x, y and z can be encoded by a higher-order function that when applied to a combinator c and a value n returns c x (c y (c z n)).
https://mcmap.net/q/1782035/-extracting-data-from-a-function-chain-without-arrays
user633183's solution is brilliant. It uses the Church encoding of lists using right folds to alleviate the need for continuations, resulting in simpler code which is easy to understand. Here's her solution, modified to make
foldrseem likefoldl:
const L = g => function (x, a) {
switch (arguments.length) {
case 1: return L((f, a) => f(g(f, a), x));
case 2: return g(x, a);
}
};
const A = L((f, a) => a);
const xs = A(1)(2)(3)(4)(5);
console.log(xs((x, y) => x + y, 0)); // 15
console.log(xs((x, y) => x * y, 1)); // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]Here
gis the Church encoded list accumulated so far. Initially, it's the empty list. Callinggfolds it from the right. However, we also build the list from the right. Hence, it seems like we're building the list and folding it from the left because of the way we write it.
If all these functions are confusing you, what user633183 is really doing is:
const L = g => function (x, a) {
switch (arguments.length) {
case 1: return L([x].concat(g));
case 2: return g.reduceRight(x, a);
}
};
const A = L([]);
const xs = A(1)(2)(3)(4)(5);
console.log(xs((x, y) => x + y, 0)); // 15
console.log(xs((x, y) => x * y, 1)); // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]As you can see, she is building the list backwards and then using
reduceRightto fold the backwards list backwards. Hence, it looks like you're building and folding the list forwards.
What I like to see in Diffrence List is
- It seems natural and straightforwad to understand.
- With concattation (flatten), it forms monoids
- Identity element is identity function, and no need for external initial values provided.
What I don't like
- At least, the sample code provided depends on JavaScript Array
What I like/dislike in Church List is, in fact, the opoosite of the above.
I like
- It's indpendent of JavaScript Array implementation, and it can define operations by itself : user633183's solution
I dislike
- I don't know why it must be not left but right fold?
a list can be encoded by identifying it with its right fold function
Unclear for the realation to Monoids
Especailly, Nil is not Identity element( = identity function), and the sample code need for external initial values provided.
So, what I am curious is is there any formalization of Diffrence list like Church-list.
The specificaton would be
Basically, it's a difference list
Indenpendent of JavaScipt Array implementation
The initial value is the built-in identety function.
Thsnk you.
