Understanding Transducers
I find that this doesn&#x27;t shed too much light for the way I think. Since I don&#x27;t have a blog let me use this comment as one:<p>If you want a significantly simpler way to &quot;understand transducers&quot;, first meditate on this TypeScript type:<p><pre><code>    type Transducer&lt;x, y&gt; = (x: x) =&gt; y[]
</code></pre>
(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&#x27;s.)<p>Transducers are applied with `flatMap`:<p><pre><code>    function transduce&lt;x, y&gt;(collection: x[], transducer: Transducer&lt;x, y&gt;): y[] {
      return collection.flatMap(transducer);
    }
</code></pre>
Some transducers of interest:<p><pre><code>    function filter&lt;x&gt;(predicate: (x: x) =&gt; boolean): Transducer&lt;x, x&gt; {
      return x =&gt; predicate(x)? [x] : []
    }

    function map&lt;x, y&gt;(fn: (x: x) =&gt; y): Transducer&lt;x, y&gt; {
      return x =&gt; [fn(x)];
    }

    function dupIf&lt;x&gt;(predicate: (x: x) =&gt; boolean): Transducer&lt;x, x&gt; {
      return x =&gt; predicate(x)? [x, x] : [x]
    }

    function compose&lt;w, x, y&gt;(
      t1: Transducer&lt;w, x&gt;,
      t2: Transducer&lt;x, y&gt;
    ): Transducer&lt;w, y&gt; {
      return w =&gt; t1(w).flatMap(t2);
    }
</code></pre>
(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&#x27;s `MonadPlus` I think?)<p>&quot;OK I understand those but I don&#x27;t see how those connect with transducers as Rich Hickey defined them.&quot; OK sure. Next thing to mediate on is that arrays traversed in sequential order are equivalent to functional stacks:<p><pre><code>    type Stack&lt;x&gt; = null | {first: x, rest: Stack&lt;x&gt; }
</code></pre>
Instead of `for (const x of array) { ... }` you would write `let s = stack; while (s !== null) { const x = s.first; s = s.rest; ... }`.<p>Since we only use transducers with flatMap which does in-order traversal of the array, we could also define `Transducer&lt;x, y&gt;` as `(x: x) =&gt; Stack&lt;y&gt;`, it&#x27;d just be less performant but the same meaning.<p>Now, the hardest part to wrap your brain around is that there is a generic way to convert a simply recursive datatype like Stack&lt;x&gt; into a type of functions. That is:<p>1. Take a fresh type-variable&#x2F;generic, call it `z`.<p>2. Request for each case of the datatype a &quot;handler&quot;, 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 `() =&gt; z` handlers can become just `z`s.<p>3. Define a function which takes these handlers and returns a `z`.<p>This is called a &quot;Church encoding&quot; after Alonzo Church, who accidentally used it to define an extremely inefficient model for the integers.<p>Used on a `Stack&lt;x&gt;` this yields:<p><pre><code>    type StackFn&lt;x&gt; = &lt;z&gt;(ifNull: z, ifStack: (first: x, rest: z) =&gt; z) =&gt; z
</code></pre>
This is basically what Array.prototype.reduceRight() does for you in JS, other languages may call these &quot;folds&quot;. Church&#x27;s inefficient model for numbers was to store them as a null[], so you can erase &quot;first: z&quot; above and rearrange as:<p><pre><code>    type Int&lt;x&gt; = &lt;z&gt;(ifGtZero: (rest: z) =&gt; z) =&gt; (ifZero: z) =&gt; z
</code></pre>
Note that this essentially takes the first input function and repeats it N times,<p><pre><code>    const zero = f =&gt; x =&gt; x;
    const one = f =&gt; x =&gt; f(x);
    const two = f =&gt; x =&gt; f(f(x));
    &#x2F;&#x2F; etc. 
</code></pre>
Serendipitously, a transducer written to output a StackFn&lt;y&gt; can similarly be transformed in a bit of a magical way, into<p><pre><code>    type TransducerFn&lt;x, y&gt; = &lt;z&gt;(ifStack: (first: y, rest: z) =&gt; z) =&gt; (x: x, ifZero: z) =&gt; z.
</code></pre>
A transducer thus takes a &quot;handler for y&#x27;s&quot; and produces a &quot;handler for x&#x27;s&quot;.<p>Note the &quot;z&quot; thread running through the middle of this, just like Church&#x27;s numbers. we sequence things into this vast composition of z =&gt; z functions.<p>Go through the cases above.<p>- Filter: &quot;I take a handler `h` for x&#x27;s, and I produce a handler for x&#x27;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).&quot;<p>- Map: &quot;I take a handler `h` for y&#x27;s, and I produce a handler for x&#x27;s which first transforms the x into a y, then sequences it into the z&#x27;s with h(f(x), z).&quot;<p>- DupIf, h(x, h(x, z)), sequence x in twice.<p>- Compose: Flipped function composition, I take a transducer t1 which transforms a handler of x&#x27;s into a handler of w&#x27;s, and another t2 which transforms a handler of y&#x27;s into a handler of x&#x27;s, and glue the input of t2 to the output of t1.