This is one of those times where types really make some equivalences clear that look completely unrelated at runtime.

The constructors for a list have the types

  Nil  : List a
  Cons : a -> List a -> List a

By a Church encoding (or more accurately a Boehm-Berarducci encoding) you end up with an equivalent higher order function that encodes a list of the following type:

  -- Boehm-Berarducci List
  type BBList a = forall b. b -> (b -> a -> b) -> b

I'm glossing over the details here, but you can basically squint and see how the first `b` corresponds to `nil` and the second to `cons` (and the two are truly equivalent, you can have functions going from `List a -> BBList a` and `BBList a -> List a` losslessly).

So what then let's plug `BBList` in for `List` in `a -> List b`.

  a -> List b
  -- BBList is equivalent to List
  a -> BBList b
  -- Expand out our definition of BBList
  -- We change type variables as necessary
  a -> forall c. c -> (c -> b -> c) -> c
  -- Remove a redundant forall (we can move all the way to the left)
  a -> c -> (c -> b -> c) -> c
  -- Rearrange arguments
  (c -> b -> c) -> c -> a -> c

And voila that's a tranducer (see https://news.ycombinator.com/item?id=8144385)!

Now that's how you could see at a glance from the types that they're equivalent. To understand what this means at runtime, it's helpful to think of the output list as the elements "you wish to keep" and everything not in that list as what you discard when composed with other transducers. So here's some transducers implemented in the direct list style.

  (defn duplicate [x] [x x])

  (defn keep-if-even [x] (if (even? x) [x] []))

  (defn map [f] (fn [x] [(f x)]))

The crucial thing (and why these transducers are still polymorphic) is that these collections are ephemeral: they go away in the final step of something like `into`.

Now composing this list-based transducers would require a special composition function (one that composes `a -> List b` with `b -> List c` to get `a -> List c`, basically `mapcat` in Clojure), but I actually regard that as a plus. It's always seemed like an accidental hack that transducers are composable with normal function composition. They compose "the wrong way" and you can't really compose them with normal functions anyways.

On a performance note, one of the reasons you'd want to use transducers is to reduce collection overhead, so you probably want to use transients since these are ephemeral anyways and you probably don't want to use actual vectors or actual lists. Instead you want to use collections that are heavily optimized for zero element, one element, and two element cases (as those are by far the most common situations you'll run into). With those optimizations in place you would have almost no new object/collection creation and I suspect that this will have better performance than the current higher order function-based implementation and top of that it'll be far simpler.

For a link that goes into greater detail about this see: https://stackoverflow.com/questions/26653829/how-is-a-transd...

I've also glossed over some details here so let me know if you want me to elaborate anywhere.

I really hope that this gets implemented at some point because current Clojure transducers seem like a wart in the language.