I find that this doesn't shed too much light for the way I think. Since I don't have a blog let me use this comment as one:
If you want a significantly simpler way to "understand transducers", first meditate on this TypeScript type:
type Transducer<x, y> = (x: x) => y[]
(Nothing special about TypeScript, I just find it easy to translate into other languages. In words, Transducer is a generic type taking two type-variables x and y, and representing the functions from an x to a list of y's.)
function filter<x>(predicate: (x: x) => boolean): Transducer<x, x> {
return x => predicate(x)? [x] : []
}
function map<x, y>(fn: (x: x) => y): Transducer<x, y> {
return x => [fn(x)];
}
function dupIf<x>(predicate: (x: x) => boolean): Transducer<x, x> {
return x => predicate(x)? [x, x] : [x]
}
function compose<w, x, y>(
t1: Transducer<w, x>,
t2: Transducer<x, y>
): Transducer<w, y> {
return w => t1(w).flatMap(t2);
}
(Theory: by the above these form a category, more precisely it is the Kleisli category for the list monad... if you drop `dupIf` which sees limited use then this is a special case of Haskell's `MonadPlus` I think?)
"OK I understand those but I don't see how those connect with transducers as Rich Hickey defined them." OK sure. Next thing to mediate on is that arrays traversed in sequential order are equivalent to functional stacks:
type Stack<x> = null | {first: x, rest: Stack<x> }
Instead of `for (const x of array) { ... }` you would write `let s = stack; while (s !== null) { const x = s.first; s = s.rest; ... }`.
Since we only use transducers with flatMap which does in-order traversal of the array, we could also define `Transducer<x, y>` as `(x: x) => Stack<y>`, it'd just be less performant but the same meaning.
Now, the hardest part to wrap your brain around is that there is a generic way to convert a simply recursive datatype like Stack<x> into a type of functions. That is:
1. Take a fresh type-variable/generic, call it `z`.
2. Request for each case of the datatype a "handler", which is a function which takes that case and returns a `z`. If that case contains a recursive reference to the datatype, the handler should take that as a `z` input. Feel free to destructure any object into arguments in the handler, and to take any `null`s and erase them, also any `() => z` handlers can become just `z`s.
3. Define a function which takes these handlers and returns a `z`.
This is called a "Church encoding" after Alonzo Church, who accidentally used it to define an extremely inefficient model for the integers.
Used on a `Stack<x>` this yields:
type StackFn<x> = <z>(ifNull: z, ifStack: (first: x, rest: z) => z) => z
This is basically what Array.prototype.reduceRight() does for you in JS, other languages may call these "folds". Church's inefficient model for numbers was to store them as a null[], so you can erase "first: z" above and rearrange as:
type Int<x> = <z>(ifGtZero: (rest: z) => z) => (ifZero: z) => z
Note that this essentially takes the first input function and repeats it N times,
const zero = f => x => x;
const one = f => x => f(x);
const two = f => x => f(f(x));
// etc.
Serendipitously, a transducer written to output a StackFn<y> can similarly be transformed in a bit of a magical way, into
type TransducerFn<x, y> = <z>(ifStack: (first: y, rest: z) => z) => (x: x, ifZero: z) => z.
A transducer thus takes a "handler for y's" and produces a "handler for x's".
Note the "z" thread running through the middle of this, just like Church's numbers. we sequence things into this vast composition of z => z functions.
Go through the cases above.
- Filter: "I take a handler `h` for x's, and I produce a handler for x's which checks x against the predicate first. If the predicate fails, just forward the z through without changing it. Otherwise change it to h(x, z)."
- Map: "I take a handler `h` for y's, and I produce a handler for x's which first transforms the x into a y, then sequences it into the z's with h(f(x), z)."
- DupIf, h(x, h(x, z)), sequence x in twice.
- Compose: Flipped function composition, I take a transducer t1 which transforms a handler of x's into a handler of w's, and another t2 which transforms a handler of y's into a handler of x's, and glue the input of t2 to the output of t1.
If you want a significantly simpler way to "understand transducers", first meditate on this TypeScript type:
(Nothing special about TypeScript, I just find it easy to translate into other languages. In words, Transducer is a generic type taking two type-variables x and y, and representing the functions from an x to a list of y's.)Transducers are applied with `flatMap`:
Some transducers of interest: (Theory: by the above these form a category, more precisely it is the Kleisli category for the list monad... if you drop `dupIf` which sees limited use then this is a special case of Haskell's `MonadPlus` I think?)"OK I understand those but I don't see how those connect with transducers as Rich Hickey defined them." OK sure. Next thing to mediate on is that arrays traversed in sequential order are equivalent to functional stacks:
Instead of `for (const x of array) { ... }` you would write `let s = stack; while (s !== null) { const x = s.first; s = s.rest; ... }`.Since we only use transducers with flatMap which does in-order traversal of the array, we could also define `Transducer<x, y>` as `(x: x) => Stack<y>`, it'd just be less performant but the same meaning.
Now, the hardest part to wrap your brain around is that there is a generic way to convert a simply recursive datatype like Stack<x> into a type of functions. That is:
1. Take a fresh type-variable/generic, call it `z`.
2. Request for each case of the datatype a "handler", which is a function which takes that case and returns a `z`. If that case contains a recursive reference to the datatype, the handler should take that as a `z` input. Feel free to destructure any object into arguments in the handler, and to take any `null`s and erase them, also any `() => z` handlers can become just `z`s.
3. Define a function which takes these handlers and returns a `z`.
This is called a "Church encoding" after Alonzo Church, who accidentally used it to define an extremely inefficient model for the integers.
Used on a `Stack<x>` this yields:
This is basically what Array.prototype.reduceRight() does for you in JS, other languages may call these "folds". Church's inefficient model for numbers was to store them as a null[], so you can erase "first: z" above and rearrange as: Note that this essentially takes the first input function and repeats it N times, Serendipitously, a transducer written to output a StackFn<y> can similarly be transformed in a bit of a magical way, into A transducer thus takes a "handler for y's" and produces a "handler for x's".Note the "z" thread running through the middle of this, just like Church's numbers. we sequence things into this vast composition of z => z functions.
Go through the cases above.
- Filter: "I take a handler `h` for x's, and I produce a handler for x's which checks x against the predicate first. If the predicate fails, just forward the z through without changing it. Otherwise change it to h(x, z)."
- Map: "I take a handler `h` for y's, and I produce a handler for x's which first transforms the x into a y, then sequences it into the z's with h(f(x), z)."
- DupIf, h(x, h(x, z)), sequence x in twice.
- Compose: Flipped function composition, I take a transducer t1 which transforms a handler of x's into a handler of w's, and another t2 which transforms a handler of y's into a handler of x's, and glue the input of t2 to the output of t1.