CODEWITHSUNDEEP
javascriptclojurefunctional-programming
AzumaO
AzumaO

Reputation: 43

Is my understanding and js code about transducer correct

web articles I've read about transducer

Js

hard to understand from half...

Clojure

I read Clojure official tutorial about 2 pages, and understood the basic syntax. I refered to built-in function reference to understand the transducer example code.

my understanding about above two article is probably 75%...

my Question

I want to know whether the following understanding/js code is correct or incorrect. Please help me.<(_ _)>

About transducer

  1. The returned value by compose() is a transducer.
  2. Transducer is executed by passed to transduce() function as argument and, in addition, (2)Transducer is executed by passing array directly to transducer().

  3. In (2)'s process, intermediate value isn't generated and efficient process like below link is performed.

my code

"use strict";

const map = fn => arr => arr.map(fn),
filter = fn => arr => arr.filter(fn),
addReducer = arr => arr.reduce((acc, num) => acc + num, 0),
add1 = n => n + 1,
even = n => n % 2 === 0,

compose = (...fns) => initVal => fns.reduce((acc, fn) => fn(acc), initVal),
transduce = (xform, reducer, arr ) => reducer( xform(arr) );



const arr = [1,2,3],
transducer = compose(  /* called transducer or xform */
   map( add1 ), // 2,3,4
   filter( even ), // 2,4
);

console.log( transducer(arr) ) // 2,4
console.log( transduce(transducer, addReducer, arr) ) // 6

Upvotes: 4

Views: 898

Answers (2)

Sylwester
Sylwester

Reputation: 48745

You code has nothing to do with transducers. Your definition of filter and m̀ap shows that it uses the normal JS filter and map

const map = fn => arr => arr.map (fn),
const filter = fn => arr => arr.filter (fn),

const combo = compose(map(add1), filter(even));
combo(arr); ==> [2, 4]

What happens is that the initial array gets passed to map with add1 which will produce the array [2, 3, 4] and then it gets passed to filter with even and a new array [2, 4] created.

The same in transducers:

const arr = [1, 2, 3];

const add1 = n => n + 1;
const even = n => n% 2 === 0;

const compose = (...fns) => {
  const [firstFunc, ...restFuncs] = fns.reverse();
  return (...args) => restFuncs.reduce((acc, fn) => fn(acc), firstFunc(...args));
};

const mapping = 
  fn => join => (acc, e) => join(acc, fn(e));

const filtering = 
  isIncluded => join => (acc, e) => isIncluded(e) ? join(acc, e) : acc;

const transducer = compose(mapping(add1), filtering(even));
const arrayJoin = (acc, e) => ([...acc, e]);
const result = arr.reduce(transducer(arrayJoin), []);
console.log(result);

So the difference is when you pass the join to the transducer it's this that happens:

mapping(add1)(filtering(even)(arrayAdd))

filtering is the only step that does add to some collection. When mapping calls join is calls filtering directly. This is why the signatures (acc, e) is the same on the work part and the join function. When the code runs the adding and filtering is done simultainiously ending up with only one generated array and no intermediate values.

Upvotes: 0

user5536315
user5536315

Reputation:

Transducers take advantage of the fact that function composition abstracts from arity, i.e. can return a function instead of a "normal value":

const comp = f => g => x => f(g(x));

const add = x => y => x + y;

const sqr = x => x * x;

const add9 = comp(add) (sqr) (3); // returns a lambda

console.log(
  add9(6)); // 15

Now a transducer itself is pretty boring:

reduce => acc => x => /* body is specific to the transducer at hand */

It is just a closure that expects a reducer (i.e. a binary function that combines its two arguments) and can then be fed directly into your favorite reducing function.

Let's take a look at the map transducer:

const mapper = f => (reduce => acc => x =>
  reduce(acc) (f(x)));

The redundant parenthesis just illustrate the transducer closure. In this case it closes over f, our transformation function. Next we are going to apply it:

// map transducer

const mapper = f => reduce => acc => x =>
  reduce(acc) (f(x));

// my favorite fold (reducing function)

const arrFold = alg => zero => xs => {
  let acc = zero;

  for (let i = 0; i < xs.length; i++)
    acc = alg(acc) (xs[i], i);

  return acc;
};

// reducer

const add = x => y => x + y;

// transformer

const sqr = x => x * x;

// MAIN

const main = arrFold(mapper(sqr) (add)) (0);

console.log(
  main([1,2,3])); // 14

Well, not that impressive, right? The real power of transducers result from their combination with function composition:

// map transducer

const mapper = f => reduce => acc => x =>
  reduce(acc) (f(x));

// filter transducer

const filterer = p => reduce => acc => x =>
  p(x) ? reduce(acc) (x) : acc;
  
// my favorite fold (reducing function)

const arrFold = alg => zero => xs => {
  let acc = zero;

  for (let i = 0; i < xs.length; i++)
    acc = alg(acc) (xs[i], i);

  return acc;
};

// helpers

const add = x => y => x + y; // reducer
const sqr = x => x * x; // transformer
const isOdd = x => (x & 1) === 1; // predicate
const comp = f => g => x => f(g(x));

// MAIN

const main = arrFold(comp(filterer(isOdd)) (mapper(sqr)) (add)) (0);

console.log(
  main([1,2,3])); // 10

Although we have two transducers involved, there is only a single traversal through the Array. This property is called loop fusion. Since the transducer composition returns another function the evaluation order is reversed, i.e. goes from left to right, whereas function composition usually goes from right to left.

Reusability is another advantage. You have to define transducers only once and can use them once and forall with all foldable data types.

It is also noteworthy that transduce is just a convenience function and isn't important to understand the concept.

That's pretty much it to say about transducers.

Upvotes: 3

Related Questions