Welcome back, let's continue from where we left of.

Follow the protocol

We know what make transducers tick, now let's find out how one might implement a transducer the right way. For this we will follow the protocol established in the transducer-js library.

The rules say that a transducer must be an object with this shape.

const transducer = {
  '@@transducer/init': function() {
    return /* ???? */;
  },
  '@@transducer/result': function(state) {
    return state;
  },
  '@@transducer/step': function(state, value) {
    // ???
  }
};

• @@transducer/init: This is where we can return an initial value, if for some reason we need one. The default behavior for this is to delegate the task to the next transducer in the composition, with a little luck someone might return something useful.

• @@transducer/result: This one runs when the process in completed. As with @@transducer/init, the default behavior that is expected is to delegate the task to the next step.

• @@transducer/step: This is where the core logic for the transducers lies. This is basically the reducer function.

We are not done yet, we also need a way to signal the end of the process and return the current value we have so far. For this, the protocol gives us a special object they call reduced. The idea is that when the reduce function "sees" this object it terminates the whole process. reduced should have this shape.

const reduced = {
  '@@transducer/reduced': true,
  '@@transducer/value': something // the current state of the process
};
A true transducer
Now it is time to apply everything we have learned so far. Let's re-implement filter, the right way. We can do it, it will mostly stay the same.

We begin with a function that returns an object.
function filter(predicate, next) {
  return {

  };
}

For the init hook, what do we need to do? Nothing, really. Then we delegate.

  function filter(predicate, next) {
    return {
+     '@@transducer/init': function() {
+       return next['@@transducer/init']();
+     },
    };
  }

When the process is completed, what do we need to do? Nothing. You know the drill.

  function filter(predicate, next) {
    return {
      '@@transducer/init': function() {
        return next['@@transducer/init']();
      },
+     '@@transducer/result': function(state) {
+       return next['@@transducer/result'](state);
+     },
    };
  }

For the grand finale, the reducer itself.

  function filter(predicate, next) {
    return {
      '@@transducer/init': function() {
        return next['@@transducer/init']();
      },
      '@@transducer/result': function(state) {
        return next['@@transducer/result'](state);
      },
+     '@@transducer/step': function(state, value) {
+       if(predicate(value)) {
+         return next['@@transducer/step'](state, value);
+       }
+
+       return state;
+     },
    };
  }

Oops, let's not forget the secret sauce.

  function filter(predicate, next) {
+   if(arguments.length === 1) {
+     return (_next) => filter(predicate, _next);
+   }

    return {
      '@@transducer/init': function() {
        return next['@@transducer/init']();
      },
      '@@transducer/result': function(state) {
        return next['@@transducer/result'](state);
      },
      '@@transducer/step': function(state, value) {
        if(predicate(value)) {
          return next['@@transducer/step'](state, value);
        }

        return state;
      },
    };
  }

We have our transducer, now we have a problem: we don't have a reduce function capable of using it.

reduce enhanced We need to do a few tweaks to our reduce.

Remember this.

function reduce(reducer, initial, collection) {
  let state = initial;

  for(let value of collection) {
    state = reducer(state, value);
  }

  return state;
}

First, we need to use the init hook.

- function reduce(reducer, initial, collection) {
+ function reduce(transducer, initial, collection) {
+   if(arguments.length === 2) {
+     collection = initial;
+     initial = transducer['@@transducer/init']();
+   }
+
    let state = initial;

    for(let value of collection) {
      state = reducer(state, value);
    }

    return state;
  }

When the function gets two arguments the collection will be stored in initial and collection will be undefined, so what we do is put initial in collection and give our transducer the chance to give us an initial state.

Next, we call the reducer function, which is now in @@transducer/step.

  function reduce(transducer, initial, collection) {
    if(arguments.length === 2) {
      collection = initial;
      initial = transducer['@@transducer/init']();
    }

    let state = initial;

    for(let value of collection) {
-     state = reducer(state, value);
+     state = transducer['@@transducer/step'](state, value);
    }

    return state;
  }

Now we need to evaluate the return value of the reducer and see if we should stop the process.

  function reduce(transducer, initial, collection) {
    if(arguments.length === 2) {
      collection = initial;
      initial = transducer['@@transducer/init']();
    }

    let state = initial;

    for(let value of collection) {
      state = transducer['@@transducer/step'](state, value);
+
+     if(state != null && state['@@transducer/reduced']) {
+       state = state['@@transducer/value'];
+       break;
+     }
    }

    return state;
  }

Lastly we need to make sure our transducer knows the process is done.

  function reduce(transducer, initial, collection) {
    if(arguments.length === 2) {
      collection = initial;
      initial = transducer['@@transducer/init']();
    }

    let state = initial;

    for(let value of collection) {
      state = transducer['@@transducer/step'](state, value);

      if(state != null && state['@@transducer/reduced']) {
        state = state['@@transducer/value'];
        break;
      }
    }

-
-   return state;
+   return transducer['@@transducer/result'](state);
  }

But I'm not done yet. There is an extra step I will like to do. You might notice that I renamed reducer to transducer, I would like for this to keep working with "normal" reducers like the ones we use with Array.reduce. So, we will create a transducer that just wraps an existent reducer.

function to_transducer(reducer) {
  if(typeof reducer['@@transducer/step'] == 'function') {
    return reducer;
  }

  return {
    '@@transducer/init': function() {
      throw new Error('Method not implemented');
    },
    '@@transducer/result': function(state) {
      return state;
    },
    '@@transducer/step': function(state, value) {
      return reducer(state, value);
    }
  };
}

Now let's use it in reduce.

  function reduce(transducer, initial, collection) {
+   transducer = to_transducer(transducer);
+
    if(arguments.length === 2) {
      collection = initial;
      initial = transducer['@@transducer/init']();
    }

    let state = initial;

    for(let value of collection) {
      state = transducer['@@transducer/step'](state, value);

      if(state != null && state['@@transducer/reduced']) {
        state = state['@@transducer/value'];
        break;
      }
    }

    return transducer['@@transducer/result'](state);
  }

Now is time to test the result of all our hard work.

const is_positive = number => number > 0;

const data = [-2, -1, 0, 1, 2, 3];
const combine = (state, value) => (state.push(value), state);

reduce(filter(is_positive, to_transducer(combine)), [], data);
// Array(3) [ 1, 2, 3 ]

Awesome, everything works just fine. But this is too much work. This is why we have that transduce helper function, but right now it's missing something, we need to add to_transducer.

function transduce(combine, initial, transducer, collection) {
  return reduce(
    transducer(to_transducer(combine)),
    initial,
    collection
  );
}

Let's go again.

const is_positive = number => number > 0;

const data = [-2, -1, 0, 1, 2, 3];
const combine = (state, value) => (state.push(value), state);

transduce(combine, [], filter(is_positive), data);
// Array(3) [ 1, 2, 3 ]

Now let's test the composition.

const is_even = number => number % 2 === 0;
const is_positive = number => number > 0;

const data = [-2, -1, 0, 1, 2, 3];
const combine = (state, value) => (state.push(value), state);

const transducer = compose(filter(is_positive), filter(is_even));

transduce(combine, [], transducer, data);
// Array [ 2 ]

You can check the full example here. I think you already have enough information to make your own transducers.

Conclusion

You made it! You reached the end of the post. I must congratulate you, specially if you understood everything in a single read, this is not an easy one. Celebrate, you deserve it.

Anyway, today we learned that transducers (in javascript) are transformations that work across multiple types of collections, as long as they provide a compatible reduce function. They also have some handy features like early termination (just like a for loop), they provide hooks that run at the beginning and end of a process, and they can compose directly just like regular functions. Lastly, in theory they also should be efficient, though they are not faster than a for loop. Regardless, they may not be the fastest things around but their compatibility with different types of collections and the declarative nature of the composition makes them a powerful tool.

Sources

• Transducers by Heiker
  • "Transducers" by Rich Hickey (video)
  • transducers-js