Clojure inspired transducers are not composable if they include a transformation

[ivenmarquardt]

As long as transducers have the type (a => t<a> => Cont<t<a>, t<a>>) => a => t<a> => Cont<t<a>, t<a>> they compose. But as soon as a transformation a => b is involved (with a map transducer for instance), they are not composable anymore, at least not with the standard HM type system.

Fortunately, scriptum is a dynamic type validator, that is to say we can manipulate type annotations at runtime arbitrarily. If special care is taken for all transforming transducers, I am confident that it is possible to restore composition as an invariant property of transducers. This will require some research, though. Bear with me.

[ivenmarquardt]

It also works if the transforming transducer comes first: A.foldk(comp(map(len)) (filter(odd)) (liftC2(A.unshift))) ([]) (["f", "fo", "foo"]).

[ivenmarquardt]

Using an Either might solve the problem but comes with an additional cognitive load. Besides it is counter-intuitive if foldk returns an Either, so it should remain local. However, this would require a spoecial fold only for transducers. Not that promising after all..

[ivenmarquardt]

There is a promising lead - higher-rank types to the rescue: (^r. (b => r => r) => a => r => r) => Transducer<a, b>.

[ivenmarquardt]

Breakthrough! We can even work with the unwrapped type (b => r => r) => a => r => r, but composition with Transducer<a, b> is a lot nicer, of course: Transducer<a, b> => Transducer<b, c> => Transducer<a, c>. I don't really understood the essence of tranducers on the term level, because I never tried to type them. On the type level this very essence is spread wide open in front of you. Types are not only safer but also more educational than dynamic environments.

[ivenmarquardt]

It is finally done:

const map = fun(
  f => cons => x => acc => Cont(fun(
    k => cons(f(x)) (acc),
    "(b => r) => r")).run(id),
  "(a => b) => (b => r => Cont<r, r>) => a => r => Cont<r, r>");

const filter = fun(
  p => cons => x => acc => Cont(fun(
    k => p(x) ? cons(x) (acc).run(k) : k(acc),
    "(a => r) => r")),
  "(a => Boolean) => (a => r => Cont<r, r>) => a => r => Cont<r, r>");

Composable just by comp without any hazzle. And we can even wrap it in the aforementioned Transducer<a, b> wrapper. HM is breath taking and although I'll never convince any JS/Node devs to take this path it is still satisfying to see what is possible.