Why does compose apply left to right with transducers?

Question

Example code:

// Compose functionality
const compose = (...fns) => {
  return args => {
    return fns.reduceRight((arg, fn) => fn(arg), args);
  }
};

// List of transformation and predicate functions
const add1 = x => x + 1;
const isGreaterThanThree = x => x > 3;
const times2 = x => x * 2;

// Concat and Sum reducers (or the thing that I want to build). 
/*
  In this case, I'm using concatReducer, but I can easily substitute concatReducer with
  sumReducer and change the initial value of the reduce method to zero.
*/
const concatReducer = (acc, el) => acc.concat(el);
const sumReducer = (acc, el) => acc += el;

// Transformation reducer (not sure the appropriate terminology)
const mapReducer = transform => {
  return reducer => {
    return (acc, el) => {
      return reducer(acc, transform(el));
    }
  }
};

// Predicate reducer (again, not sure the appropriate terminology here)
const filterReducer = predicate => {
  return reducer => {
    return (acc, el) => {
      return predicate(el) ? reducer(acc, el) : acc;
    }
  }
}

[1, 2, 3] 
  .reduce(
    compose(
      mapReducer(times2),
      filterReducer(isGreaterThanThree),
      mapReducer(add1),
    )(concatReducer),
    []
  );

I expect the value to be [ 8 ] instead of [ 5, 7 ].

Compose is a right-associative (reduceRight), but in this case, it is behaving as left-associative.

I thought to myself that maybe my compose function implementation was wrong. As a result, I pulled in ramda.js and used R.compose, but I got the same result.

Am I doing something wrong? Or is this one of those scenarios that compose is left-associative when dealing with transducers?

Answer 1

Quotes and some of the examples are taken from https://github.com/cognitect-labs/transducers-js.

What is a transducer?

Transducers are simply a function of one arity. The only argument is another transducer transformer (labeled xf in the code base).

Since transducers are simply functions of one argument they can be composed easily via function composition to create transformer pipelines. Note that transducers return transformers when invoked.

Example: (adapted)

var mapper = function(f) {
  return function(xf) {    // <- This is a transducer, it takes a transformer xf
    return Mapper(f, xf);  // <- and it returns another transformer xf'
  };
};

Note: we'll cover Mapper later.

Let's rewrite with some arrow functions:

var mapper = f => xf => Mapper(f, xf);
//                ^^^^^^^^^^^^^^^^^^^
//                This is a transducer

In the snippet above it should be clearer that a transducer is indeed a function that takes a transformer and returns another transformer. These two compositions are equal:

compose(mapper(double), mapper(inc))

compose(xf => Mapper(double, xf), xf => Mapper(inc, xf))

Fun fact

The function composition now waits for the initial transformer which is commonly referred to as the "step" transformer (or "step" function) which is responsible for accumulating the transformation into a container.

A typical container would be either an array, a string or an object. Such "step" transformer would either:

• push to an array (we'll refer to such transformer as Push in the rest of this answer)
• or append to a string
• or set a property on a object

But we don't need to know the details of such transformer. However we do need to understand what transformers are.

What is a transformer?

Transformers are objects. They must implement 3 methods, @@transducer/init, @@transducer/result and @@transducer/step. If a transformer is intended to be composed with other transformers they should either close over the next transformer or store it in a field.

Example: (adapted)

var Mapper = function(f, xf) {
  return { // <-- This is a transformer
    "@@transducer/init": function() { 
      return xf["@@transducer/init"](); 
    },
    "@@transducer/result": function(result) { 
      return xf["@@transducer/result"](result); 
    },
    "@@transducer/step": function(result, input) {
      return xf["@@transducer/step"](result, f(input));
      //                                     ^^^^^^^^
      //                                     e.g. inc(41)
    }
  };
};

In order to understand why transducers reverse the order of the composition, we need to take a closer look at the @@transducer/step method:

"@@transducer/step": function(result, input) {
  return xf["@@transducer/step"](result, f(input));
//       ^^^^^^^^^^^^^^^^^^^^^^^         ^
//       called last                     called first!

Note: result is the container into which we will accumulate the transformations.

When you do:

compose(mapper(double), mapper(inc))(Push())

You end up with a final transformer that looks like this:

const xfinal = Mapper(double, Mapper(inc, push));

Usually your library will do this for you but for educational purpose we will call the the @@transducer/step method on that final transformer and decompose the functions calls:

xfinal['@@transducer/step']([], 20)

Is similar to:

Mapper(double, Mapper(inc, push))([], 20)
       ^^^^^^  ^^^^^^^^^^^^^^^^^
       f       xf

Mapper(inc, push)([], double(20))
^^^^^^^^^^^^^^^^^
xf     ^^^  ^^^^
       f'   xf'

push([], inc(double(20)))
^^^^     ^^^ ^^^^^^
xf'      f'  f
         ^^^^^^^^^^^^^^^
         HERE!

Even though we did compose(mapper(double), mapper(inc)) we can see that the double function got applied before inc did. This isn't a bug in the compose function, it is simply how transformers are supposed to work when composed together.

Answer 2

Because you apply the composed transducers (f,g,h) to a reducer (r), the leftmost (f) becomes topmost, first to act on the eventual arguments (acc, el) to the augmented reducer f( g(h(r)) ):^(*)

compose(f,g,h)(r)(acc, el) =~= f( g( h( r)) )(acc, el)
                                  <--------
                               --...........->

Indeed the rightmost, h, is applied to the argument r first; but that r is also a function; the whole composed thing is a function; and the composed function has f as its first component, so it is f that gets to work on the next arguments (acc, el) first, using the result of the inner composition g( h( r)) according to the definition of f.

What we have here, is

       r        //  reducer
    h           // transducer
    h( r )      //  reducer
  g             // transducer
  g(h( r ))     //  reducer
f               // transducer
f(g(h( r )))    //  reducer

---

^(*) So you have defined your functions so that

mapReducer(foo)(reducer)(acc, el) 
  =~= reducer(acc, foo(el));

filterReducer(predicate)(reducer)(acc, el)
  =~= predicate(el) ? reducer(acc, el) : acc;

concatReducer(acc, el)
  =~= acc.concat(el);

and, most importantly,

compose(f,g,h,...,p,q)(r)
    =~= [f,g,h,...,p,q].reduceRight((acc, fn) => fn(acc), r);
    =~= f(g(h(...(p(q( r ))...)))

So then

[1, 2, 3] 
  .reduce(
    compose(
      f,               // f = mapReducer(times2),
      g,               // g = filterReducer(isGreaterThanThree),
      h                // h = mapReducer(add1),
      )(r),            // r = concatReducer
    []
  )
  =~= [1, 2, 3] .reduce( f(g(h(r))), [])     // rc = f(g(h(r)))
  =~= rc( rc( rc( [], 1),  2),  3)
  =~= rc( rc( f(g(h(r)))( [], 1),  2),  3)
  =~= rc( rc( mapReducer(times2)(g(h(r)))( [], 1 ),  2),  3)

           // mapReducer(foo   )(reducer)(acc, el)
           //                =~= reducer( acc, foo(el))

  =~= rc( rc( g(h(r))([], times2( 1)),  2),  3)
  =~= rc( rc( filterReducer(isGreaterThanThree)(h(r))([] , times2( 1)),  
            2), 
        3)

           // filterReducer(pred           )(reducer)(acc, el)
           //                =~= pred(el) ?  reducer( acc, el) : acc

  =~= rc( rc( isGreaterThanThree( twice1) ? h(r)(  [], twice1) : [],  
            2),          /* where twice1 = times2(1) 
                                  h = mapReducer( add1) */
        3)
  =~= rc( rc( isGreaterThanThree( twice1) ? r([], add1(twice1)) : [],  
            2),          /* where twice1 = times2(1) 
                                  r = concatReducer  */
        3)
  =~= rc( rc( isGreaterThanThree( twice1) ? [].concat(add1(twice1)) : [],  
            2),          /* where twice1 = times2(1) */
        3)
  =~= ...

and we can see that mapReducer(times2) gets to work on the list's elements first, before the filtering by isGreaterThanThree and then the mapping of add1.

In processing the [1,2,3], first the mapping of times2 is done (implicitly as-if making it [2,4,6]), then the filtering (which would leave just [4,6]), and then the mapping of add1, for the final result of [5,7] indeed.

There's no creating the interim structure though. Instead one composite reducer is built, and used by one reduce, advancing along the input one step at a time.

Thus transducers are a fusion / deforestation technique. Intuitively, nested folds should fuse, eliminating the need for the interim structure creation by an inner fold only so it can be consumed by the wrapping fold; following the transducer discipline lets us achieve just that.

---

So then, mapReducer and filterReducer are badly named. They are actually mappingTransducer_Maker (or just mapping) and filteringTransducer_Maker (or just filtering), where

• mapping(foo) is a mapping transducer that applies foo to the input's element elt, resulting in foo(elt), and
• filtering(pred) is a filtering transducer that filters out the input's element el according to the predicate call pred(el), or keeps it in.

Or rather, a transducer augments its argument reducer so that when the combined, augmented reducer is finally called with the accumulator and the current element, it manipulates the element and the accumulator in a prescribed way before passing the results to the base reducer:

mapping(foo)( filtering(pred)(reducer) )( acc, elt)
----------------------------------------(         )
 =~=
filtering(pred)(reducer)( acc, foo(elt) )
 =~=
pred( foo(elt) ) ? reducer( acc, foo(elt) ) : acc

So, mapping(foo) and filtering(pred) are composed right-to-left with respect to their argument, reducer; but then the composed reducer starts working from the top, tracing the transducers' effects left-to-right -- first doing the mapping, and doing the filtering after that.