5 ms·

Understanding Transducers

40 points by signa11 4y ago

endgame 4y ago
I find the following type signature captures the essence: type Transducer x y = forall b. (b -> y -> b) -> (b -> x -> b) https://github.com/bitemyapp/learnhaskell/blob/master/dialogues.md#transducers https://github.com/bitemyapp/learnhaskell/blob/master/dialog...
- crdrost 4y ago
  Thanks for this link!
crdrost 4y ago
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.) Transducers are applied with `flatMap`: function transduce<x, y>(collection: x[], transducer: Transducer<x, y>): y[] { return collection.flatMap(transducer); } Some transducers of interest: 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.
kiprasmel 4y ago
i really liked getify's explanation in his functional-light javascript book: https://github.com/getify/Functional-Light-JS/blob/40a68612275b23904c7b37abdb724b250bdf75e7/manuscript/apA.md https://github.com/getify/Functional-Light-JS/blob/40a686122...

40 points by signa11 4y ago

I find the following type signature captures the essence: type Transducer x y = forall b. (b -> y -> b) -> (b -> x -> b) https://github.com/bitemyapp/learnhaskell/blob/master/dialogues.md#transducers https://github.com/bitemyapp/learnhaskell/blob/master/dialog...

crdrost 4y ago
Thanks for this link!

crdrost 4y ago

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.) Transducers are applied with `flatMap`: function transduce<x, y>(collection: x[], transducer: Transducer<x, y>): y[] { return collection.flatMap(transducer); } Some transducers of interest: 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.

kiprasmel 4y ago

i really liked getify's explanation in his functional-light javascript book: https://github.com/getify/Functional-Light-JS/blob/40a68612275b23904c7b37abdb724b250bdf75e7/manuscript/apA.md https://github.com/getify/Functional-Light-JS/blob/40a686122...