A "construction" is how you make a new combinator out of existing combinators. This one expects two quoted values—"A" and "B"—and processes them with the commented combinators shown.
The Euclidean Division combinator is provisionally named a "construction." […]
[Original post on functional.cafe]
![import { A } from "../combinator-tools/placeholders";
import { proper } from "../combinator-tools/propriety";
export const m = proper([ [A] ], [ [A], A ]);](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreiawzeguygeiuadcrr5cf7zjmbgvenxpmg35mgaym7fsb7sko7peai)
![// n.b. returns quoted numbers, not applicable numbers,
// as it is necessary to select whether one wants the quotient, remainder, or both.
const euclideanDividedBy = construction([ [B], [A] ], [
[zero], bury, // [quotient] [dividend] [divisor]
[
bury3, // [callback] [quotient] [dividend] [divisor]
dup, // [callback] [quotient] [dividend] [divisor] [divisor]
[swap], dip, // [callback] [quotient] [divisor] [dividend] [divisor]
[dup], dip, // [callback] [quotient] [divisor] [dividend] [dividend] [divisor]
isLessThan, // [callback] [quotient] [divisor] [dividend] [T/F: dividend < divisor]
[
// [callback] [quotient] [divisor] [dividend]
[[minus], cons, cons], sip, // [callback] [quotient] [dividend - divisor] [divisor]
dig2, // [callback] [dividend - divisor] [divisor] [quotient]
[succ], cons, // [callback] [dividend - divisor] [divisor] [quotient++]
bury2, // [callback] [quotient++] [dividend - divisor] [divisor]
dig3, // [quotient++] [dividend - divisor] [divisor] [callback]
m
],
[
// [callback] [quotient] [divisor] [dividend]
nip, // [callback] [quotient] [dividend]
dig2, zap // [quotient] [dividend]
],
cond // [quotient] [remainder]
],
m, // [quotient] [remainder]
]);](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreie4fkqktvzzsuq55r4stoeojyqio5enaubjvpeoiemal6afeiwwyy)
![// [B] [A] And == [B && A]
test("boolean and", () => {
expect(display(rewrite([ [False], [False], And ]))).toEqual(display(rewrite([ [False] ])));
expect(display(rewrite([ [False], [True], And ]))).toEqual(display(rewrite([ [False] ])));
expect(display(rewrite([ [True], [False], And ]))).toEqual(display(rewrite([ [False] ])));
expect(display(rewrite([ [True], [True], And ]))).toEqual(display(rewrite([ [True] ])));
});
// [B] [A] Or == [B || A]
test("boolean or", () => {
expect(display(rewrite([ [False], [False], Or ]))).toEqual(display(rewrite([ [False] ])));
expect(display(rewrite([ [False], [True], Or ]))).toEqual(display(rewrite([ [True] ])));
expect(display(rewrite([ [True], [False], Or ]))).toEqual(display(rewrite([ [True] ])));
expect(display(rewrite([ [True], [True], Or ]))).toEqual(display(rewrite([ [True] ])));
});
// [A] Not == [¬A]
test("boolean not", () => {
expect(display(rewrite([ [False], Not ]))).toEqual(display(rewrite([ [True] ])));
expect(display(rewrite([ [True], Not ]))).toEqual(display(rewrite([ [False] ])));
});
// [B] [A] Xor == [(B || A) && ¬(B && A)]
test("boolean or", () => {
expect(display(rewrite([ [False], [False], Xor ]))).toEqual(display(rewrite([ [False] ])));
expect(display(rewrite([ [False], [True], Xor ]))).toEqual(display(rewrite([ [True] ])));
expect(display(rewrite([ [True], [False], Xor ]))).toEqual(display(rewrite([ [True] ])));
expect(display(rewrite([ [True], [True], Xor ]))).toEqual(display(rewrite([ [False] ])));
});](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreicxis6ini7ovwo4nhaw3swqtvevxrdo7ppumyuwhbjivdqaxoy64e)
![export const times = b;
export const plus = construction([ [cons, b], cons, s ]);
export const exponent = i;
export const succ = construction([ [z1], plus ]);
export const pred = construction([
// initialization
[[z0], [z0]],
// [[__], [Zn]] => [Zn], [++Zn]
[i, nip, dup, [succ], cons],
// dig the quoted parameter up: [C] [B] [A] => [B] [A] [C]
dig,
// apply it, counting up: [z0], [z0] => [z0], [z1] => [z1], [z2] => [z2], [z3], ...
i,
// discard the rightmost quoted number, revealing the quoted predecessor
zap,
// apply it
i
]);
test("pred", () => {
expect((rewrite([[[]], [unit], [z0], pred]))).toEqual(rewrite([[[]], [unit], z0]));
expect((rewrite([[[]], [unit], [z1], pred]))).toEqual(rewrite([[[]], [unit], z0]));
expect((rewrite([[[]], [unit], [z2], pred]))).toEqual(rewrite([[[]], [unit], z1]));
expect((rewrite([[[]], [unit], [z3], pred]))).toEqual(rewrite([[[]], [unit], z2]));
expect((rewrite([[[]], [unit], [z4], pred]))).toEqual(rewrite([[[]], [unit], z3]));
});](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreigam5tt37az5nilpbazhck52dw442x3tm37wf53cyl6drktdqxnxe)
![test("product", () => {
expect(rewrite([ [], [unit], [z0], [z3], product ])).toEqual(rewrite([ [], [unit], z0 ]));
expect(rewrite([ [], [unit], [z3], [z0], product ])).toEqual(rewrite([ [], [unit], z0 ]));
expect(rewrite([ [], [unit], [z1], [z5], product ])).toEqual(rewrite([ [], [unit], z5 ]));
expect(rewrite([ [], [unit], [z5], [z1], product ])).toEqual(rewrite([ [], [unit], z5 ]));
expect(rewrite([ [], [unit], [z2], [z3], product ])).toEqual(rewrite([ [], [unit], z6 ]));
expect(rewrite([ [], [unit], [z3], [z2], product ])).toEqual(rewrite([ [], [unit], z6 ]));
});
test("sum", () => {
expect(rewrite([ [], [unit], [z0], [z3], sum ])).toEqual(rewrite([ [], [unit], z3 ]));
expect(rewrite([ [], [unit], [z3], [z0], sum ])).toEqual(rewrite([ [], [unit], z3 ]));
expect(rewrite([ [], [unit], [z1], [z5], sum ])).toEqual(rewrite([ [], [unit], z6 ]));
expect(rewrite([ [], [unit], [z5], [z1], sum ])).toEqual(rewrite([ [], [unit], z6 ]));
expect(rewrite([ [], [unit], [z2], [z3], sum ])).toEqual(rewrite([ [], [unit], z5 ]));
expect(rewrite([ [], [unit], [z3], [z2], sum ])).toEqual(rewrite([ [], [unit], z5 ]));
});
test("exponent", () => {
expect(rewrite([ [], [unit], [z2], [z0], exponent ])).toEqual(rewrite([ [], [unit], z1 ]));
expect(rewrite([ [], [unit], [z2], [z1], exponent ])).toEqual(rewrite([ [], [unit], z2 ]));
expect(rewrite([ [], [unit], [z2], [z2], exponent ])).toEqual(rewrite([ [], [unit], z4 ]));
expect(rewrite([ [], [unit], [z2], [z3], exponent ])).toEqual(rewrite([ [], [unit], z8 ]));
expect(rewrite([ [], [unit], [z3], [z2], exponent ])).toEqual(rewrite([ [], [unit], z9 ]));
});](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreiec2jhfcepaw6xkueuiuitxaw6cgqyhkozgtqvsslneu3yh5xliiu)
![// [C] [B] [A] s == [[C] B] [C] A
export const s = combinator((C: Quotation, B: Quotation, A: Quotation) => [ [C, ...B], C, ...A ]);
export const starling = s;
// [B] [A] k == A
export const k = combinator((B: Quotation, A: Quotation) => [ ...A ]);
export const kestrel = k;](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreiewblb5opxs26itxj3mpszjaqyic6qmei2u7xic7zofmw7ujli27a)
![test("zn", () => {
expect(z0([ [z0], [z1] ])).toEqual([ z0 ]);
expect(z1([ [z0], [z1] ])).toEqual([ [ z0 ], z1 ]);
expect(z2([ [z0], [z1] ])).toEqual([ [ [ z0 ], z1 ], z1 ]);
expect(z3([ [z0], [z1] ])).toEqual([ [ [ [ z0 ], z1 ], z1 ], z1 ]);
expect(z4([ [z0], [z1] ])).toEqual([ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ]);
expect(z5([ [z0], [z1] ])).toEqual([ [ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ], z1 ]);
expect(z6([ [z0], [z1] ])).toEqual([ [ [ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ]);
expect(z7([ [z0], [z1] ])).toEqual([ [ [ [ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ]);
expect(z8([ [z0], [z1] ])).toEqual([ [ [ [ [ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ]);
expect(z9([ [z0], [z1] ])).toEqual([ [ [ [ [ [ [ [ [ [ z0 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ], z1 ]);
});](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreiapiw4qcccf7ewmttazpi2to3256jdzxj7zdcoe7fodxrwtqy2a7y)
![// [B] [A] cons == [[B] A]
export const cons = combinator((B: Parameter, A: Parameter) => {
if (!isProgram(A)) return Fail;
if (!isProgram(B)) return Fail;
if (A.length === 0) return Fail;
if (B.length === 0) return Fail;
return [ [B, ...A] ];
});](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreicgxmuu5kwdyqocdlvbzzrpniq3cw4abij4wgin4bice4fxudygga)
![### the list interpretation of balanced parentheses
Chaining cons cells together by the `cdr` pointer creates a list. For example, this is a list of five holes —`()()()()()`—diagrammed to show the links:
```mermaid
graph LR
EmptyPair@{ shape: dbl-circ, label: "()" }
Five(["()()()()()"]) --> Four(["()()()()"])
Four --> Three(["()()()"])
Three --> Two(["()()"])
Two --> EmptyPair
```
We don't call it a list of empty pairs. The pairs we write in text notation are containers, and if the pairs contain empty, than we say this is a list of five holes.
A list of five empty pairs looks like this:
```mermaid
graph TD
EmptyPair@{ shape: dbl-circ, label: "()" }
Five(["(())(())(())(())(())"]) --o EmptyPair
Five --> Four(["(())(())(())(())"])
Four --o EmptyPair
Four --> Three(["(())(())(())"])
Three --o EmptyPair
Three --> Two(["(())(())"])
Two --o EmptyPair
Two --> One(["(())"])
One --o EmptyPair
```](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreiep2bm4ce7kdxdz2k7bg6k4t7rkjzcuuksbjqmd4xo5lkls3kruhe)
![### the cons cell interpretation of balanced parentheses
An empty pair of parentheses is a cons cell with both its `car` and `cdr` pointing to the empty string (`ε`). The `car` pointer terminates in a circle, the `cdr` pointer terminates in an arrow.
```mermaid
graph LR
A(["()"]) -- car --o E:::transparent@{ shape: circ, label: "ε" }
A -- cdr --> E
classDef transparent stroke:#ffffff, fill: #ffffff
```
Either or both can point to another cons cell:
```mermaid
graph LR
B(["(())"]) -- car --o A
B(["(())"]) -- cdr --> E
A(["()"]) -- car --o E:::transparent@{ shape: circ, label: "ε" }
A -- cdr --> E
classDef transparent stroke:#ffffff, fill: #ffffff
```
```mermaid
graph LR
C(["()()"]) -- car --o E
C(["()()"]) -- cdr --> A
A(["()"]) -- car --o E:::transparent@{ shape: circ, label: "ε" }
A -- cdr --> E
classDef transparent stroke:#ffffff, fill: #ffffff
```
```mermaid
graph LR
D(["(())()"]) -- car --o A
D(["(())()"]) -- cdr --> A
A(["()"]) -- car --o E:::transparent@{ shape: circ, label: "ε" }
A -- cdr --> E
classDef transparent stroke:#ffffff, fill: #ffffff
```](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreib3puribiy3hpgw4ftnvnfqqdctplnk7ray53czr4ankecrg4hk3q)
![// ---------- The Why Bird as an HKT ----------
//
// This is a nearly direct translation of a JS
// implementation from "Why Y? Deriving the
// Y Combinator in JavaScript:"
//
// https://raganwald.com/2018/09/10/why-y.html
//
// const Y =
// fn =>
// M(m => a => fn(m(m))(a));
// A kind that encapsulates the "maker" function within the Why Brd
type _$Maker<FN extends HigherOrderKind, M extends HigherOrderKind, A> =
$< FN,_$cast<_$M<M>, _$inputOf<FN>> > extends infer InnerMaker extends Kind.Kind
? $< InnerMaker, _$cast<A, _$inputOf<InnerMaker>> >
: never;
interface Maker_T<FN extends HigherOrderKind, M extends HigherOrderKind> extends Kind.Kind {
f(
a: this[Kind._]
): _$Maker<FN, M, typeof a>
}
interface Maker<FN extends HigherOrderKind> extends Kind.Kind {
f(
m: _$cast<this[Kind._], HigherOrderKind>
): Maker_T<FN, typeof m>
}
// The Why Bird composes a decoupled recursive kind with itself,
// converting a decoupled recursive kind to a recurive kind
interface Y extends Kind.Kind {
f(
fn: _$cast<this[Kind._], Kind.Kind>
): _$M<Maker<typeof fn>>
}](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreifunbhkbwdua33anhvtlk6awdih3q623rc243bohcftwkedfdpg2u)
![type M<K extends Kind.Kind> = $<K, Type._$cast<K, _$inputOf<K>>>;
type LastButLast<S extends string, AccumulatedButLast extends string> =
$N<M<LastButLastKind>, [S, AccumulatedButLast, NewCounter]> extends infer Result
? Result extends { type: ContinuationType, parameters: [infer NewS extends string, infer NewAccumulatedButLast extends string] }
? LastButLast<NewS, NewAccumulatedButLast>
: Result
: never;
type _$LastButLast<K extends LastButLastKind, S extends string, AccumulatedButLast extends string, RecursionCount extends Counter> =
S extends `${infer Head}${infer ButHead}`
? ButHead extends ""
? [Head, AccumulatedButLast]
: Count<RecursionCount> extends RecursionLimit
? ContinueWith<[S, AccumulatedButLast]>
: $N<M<LastButLastKind>, [ButHead, `${AccumulatedButLast}${Head}`, Increment<RecursionCount>]>
: ["", ""]](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreie5v3wddfavvlzrmysn2gqgtbb7eaxjvz7pifxmysnky2pf6r4szi)
![const BookCollector = {
addToCollection (name) {
this.collection().push(name);
return this;
},
collection () {
return this._collected_books || (this._collected_books = []);
}
};
class Person {
constructor (first, last) {
this.rename(first, last);
}
fullName () {
return this.firstName + " " + this.lastName;
}
rename (first, last) {
this.firstName = first;
this.lastName = last;
return this;
}
};
Object.assign(Person.prototype, BookCollector);](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:tdu2ua5n5twpnw3w3nzqe6pq/bafkreibch455jzgi542pxlvo5txyuzczmbevh34w42d5mrsvwk2yrpg7ae)
