Order of Execution of Composed Function

Question

I have been reading up on transducers and playing around trying to grasp the concept. I now understand them a bit, but during my fiddling, I came across something very peculiar that has me dumbfounded. I'm hoping someone can explain what I'm missing.

I have 2 transducers that have the signature: reducer -> reducer

I also have a simple compose function: const compose = (f, g) => x => f(g(x))

When I compose the 2 transducers:

const filterLessThanThreeAndMultiply = compose(
  filteringReducer(lessThanThreePredicate),
  mappingReducer(multiplyTransform)
)

I would expect the evaluation to be from right to left, in this case applying the mapping transform before the filtering. Instead, the filtering is applied first (which gives the expected answer).

But f(g(x)) runs f of the result of g(x), so my result should reflect:

filteringReducer(lessThanThreePredicate)(mappingReducer(multiplyTransform)
(concatTransducer))

But instead it reflects (correctly):

mappingReducer(multiplyTransform)(filteringReducer(lessThanThreePredicate)
(concatTransducer))

(See code below)

Why??!! (I suspect I'll make a quantum leap in understanding once someone explains to me what's happening here).

const filteringReducer = predicate => transducer => (result, input) =>
  predicate(input) ? transducer(result, input) : result

const mappingReducer = transform => transducer => (result, input) =>
  transducer(result, transform(input))

const compose = (f, g) => x => f(g(x))

const concatTransducer = (a, b) => a.concat([b])

const lessThanThreePredicate = x => x < 3
const multiplyTransform = x => x * 100

const filterLessThanThreeAndMultiply = compose(
  filteringReducer(lessThanThreePredicate),
  mappingReducer(multiplyTransform)
)

const result = [-2, -1, 0, 1, 2, 3, 4].reduce(
  filterLessThanThreeAndMultiply(concatTransducer),
  []
)

console.log('result ', result)  // [-200, -100, 0, 100, 200]

Answer 1

You are seeing the filter happen (correctly) before the map even though they are both inside compose because of an implementation detail of transducers. I will explain by breaking down transducers in implementation and then showing you how to use them.

Consider the following variants of map and filter

const mapArray = fn => array => array.map(fn) // map for arrays
const filterArray = fn => array => array.filter(fn) // filter for arrays

const mapReducer = fn => reducer => (y, xi) => reducer(y, fn(xi)) // map for reducers
const filterReducer = fn => reducer => (y, xi) => fn(xi) ? reducer(y, xi) : y // filter for reducers

1. mapArray takes a function fn and an array and returns another array with fn applied to each element.
2. filterArray takes a function fn and an array and return another array filtered by fn
3. mapReducer takes a function fn and returns reducer => (y, xi) => {...}
4. filterReducer takes a function fn and returns reducer => (y, xi) => {...}

Now, consider the transducer signature

transducers have the signature: reducer -> reducer

Given (y, xi) => {...} is just another reducer, this means mapReducer(multiplyTransform) and filterReducer(lessThanThreePredicate) are both transducers.

Great! So now we know what transducers are, but how do we use them?

Exhibit A (no compose)

const x100Transducer = mapReducer(x => x * 100)

const lessThanThreeTransducer = filterReducer(x => x < 3)

const concat = (y, xi) => y.concat([xi])

const finalReducerLessThanThreeThenX100ThenConcat = (y, xi) => (
  lessThanThreeTransducer( // this is called with (y, xi) first
    x100Transducer( // then this
      concat // finally this
    )
  )(y, xi)
)

[1, 2, 3, 4, 5].reduce(finalReducerX100ThenConcat, []) // => [100, 200]

In order to set up our transducers so that we first filter x => x < 3 and then map x => x * 100, we must compose our transducers lessThanThreeTransducer and x100Transducer as we have done above. Now, if we toss in compose, you will have your answer as to why everything seems backwards.

Exhibit B (with compose)

const x100Transducer = mapReducer(x => x * 100)

const lessThanThreeTransducer = filterReducer(x => x < 3)

const concat = (y, xi) => y.concat([xi])

const compose = (f, g) => x => f(g(x)) // f is lessThanThreeTransducer, g is x100Transducer
// x is concat (compare to above)

const finalComposedReducer = compose(lessThanThreeTransducer, x100Transducer)(concat)

[1, 2, 3, 4, 5].reduce(finalComposedReducer, []) // => [100, 200]

Indeed, finalComposedReducer and finalReducerLessThanThreeThenX100ThenConcat are algorithmically equivalent. So then,

Why??!!

It's an implementation detail of transducers. If you're still curious about transducers, I write more about them here.