javascriptrecursionreducecontinuation-passingtransducer

Why doesn't my transducer work anymore when abstracting from reducing/composing?


I am stuck with my short circuiting and stack safe transducer implementation:

const loop = f => {
   let acc = f();

   while (acc && acc.type === tailRec)
     acc = f(...acc.args);

   return acc;
};

const tailRec = (...args) =>
   ({type: tailRec, args});

const arrFoldk = f => acc_ => xs =>
  loop((acc = acc_, i = 0) =>
    i === xs.length
      ? acc
      : f(acc) (xs[i]) (acc_ => tailRec(acc_, i + 1)));

const liftk2 = f => x => y => k =>
  k(f(x) (y));

const isOdd = n => n & 1 === 1;
const concat = xs => ys => xs.concat(ys);
const comp = f => g => x => f(g(x));
const id = x => x;

const filterReduce = filter => reduce => acc => x => k =>
  filter(x)
    ? reduce(acc) (x) (k)
    : k(acc);

const takeReduce = n => reduce => acc => x => k =>
  acc.length === n
    ? reduce(acc) (x) (id)
    : reduce(acc) (x) (k);

const fx = filterReduce(isOdd),
  fy = takeReduce(3),
  fz = comp(fy) (fx);

const transducek = (...fs) => xs =>
  arrFoldk(fs.reduce((f, g) => comp(f) (g), id) (liftk2(concat))) ([]);

const r1 = arrFoldk(fz(liftk2(concat))) ([]) ([1,2,3,4,5,6,7,8,9]);
const r2 = transducek(fx, fy) ([1,2,3,4,5,6,7,8,9]);

console.log(r1); // [1,3,5]
console.log(r2); // xs => ...

I am looking at the code and it tells me quite clearly that the computations yielding r1 and r2, respectively, are essentially the same. Why don't I get the same result when applying the transduce auxiliary function?


Solution

  • Not sure if these are the errors you're looking for, but these two things struck me:

    1. You've included xs in the signature of transduceK, but never call the composed function with this parameter. Either add (xs) to the end, or just do:

      const transducek = (...fs) =>
        arrFoldk(fs.reduce((f, g) => comp(f) (g), id) (liftk2(concat))) ([]);
      
    2. The equivalent of comp (fy) (fx) is [fx, fy].reduceRight((g, h) => comp (g) (h), id) or [fx, fy].reduce((f, g) => comp(g) (f), id)

    With these changes, I think everything works as intended:

    const loop = f => {
       let acc = f();
    
       while (acc && acc.type === tailRec)
         acc = f(...acc.args);
    
       return acc;
    };
    
    const tailRec = (...args) =>
       ({type: tailRec, args});
    
    const arrFoldk = f => acc_ => xs =>
      loop((acc = acc_, i = 0) =>
        i === xs.length
          ? acc
          : f(acc) (xs[i]) (acc_ => tailRec(acc_, i + 1)));
    
    const liftk2 = f => x => y => k =>
      k(f(x) (y));
    
    const isOdd = n => n & 1 === 1;
    const concat = xs => ys => xs.concat(ys);
    const comp = f => g => x => f(g(x));
    const id = x => x;
    
    const filterReduce = filter => reduce => acc => x => k =>
      filter(x)
        ? reduce(acc) (x) (k)
        : k(acc);
    
    const takeReduce = n => reduce => acc => x => k =>
      acc.length === n
        ? reduce(acc) (x) (id)
        : reduce(acc) (x) (k);
    
    const fx = filterReduce(isOdd),
      fy = takeReduce(3),
      fz = comp(fy) (fx);
    
    const transducek = (...fs) =>
      arrFoldk(fs.reduce((f, g) => comp(g) (f), id) (liftk2(concat))) ([]);
    
    const r1 = arrFoldk(fz(liftk2(concat))) ([]) ([1,2,3,4,5,6,7,8,9]);
    const r2 = transducek(fx, fy) ([1,2,3,4,5,6,7,8,9]);
    
    console.log(r1); // [1,3,5]
    console.log(r2); // [1,3,5]