¿Cómo implementar una función de reducción más general para permitir la salida anticipada?
reduce
(tambien conocido comofoldL
en FP) es la función iterativa de orden superior más general en Javascript. Puede implementar, por ejemplo,map
ofilter
en términos dereduce
. He usado un bucle imperativo para ilustrar mejor el algoritmo:
const foldL = f => acc => xs => {
for (let i = 0; i < xs.length; i++) {
acc = f(acc)(xs[i]);
}
return acc;
};
const map = f => xs => {
return foldL(acc => x => acc.concat([f(x)]))([])(xs);
}
let xs = [1, 2, 3, 4];
const inc = x => ++x;
map(inc)(xs); // [2, 3, 4, 5]
Pero no puedes derivarsome
oevery
dereduce
, porque ambos pueden regresar temprano.
Entonces, ¿cómo puede ser una función de reducción parcial aún más generalizada? Hasta ahora se me ocurrió la siguiente implementación ingenua:
const foldLP = f => pred => acc => xs => {
for (let i = 0, r; i < xs.length; i++) {
r = pred(i, acc, xs[i]);
if (r === true) { // normal iteration
acc = f(acc)(xs[i]);
} else if (r === false) { // early exit
break;
} /* else { // skip iteration
continue;
} */
}
return acc;
};
const takeN = n => (idx, acc, x) => idx < n;
const append = xs => ys => xs.concat(ys);
let xs = [1,2,3,4,5];
foldLP(append)(takeN(3))([])(xs); // [1,2,3]
También puedo implementarmap
en términos defoldLP
:
const always = x => y => x;
const map = f => xs => {
return foldLP(acc => x => acc.concat([f(x)]))(always(true))([])(xs);
}
map(inc)(xs); // [2,3,4,5,6]
El inconveniente es obvio: cuando no se necesita un mecanismo de salida anticipada,always
se invoca innecesariamente. La función de transformación y salida temprana está compuesta estáticamente porfoldLP
y no se puede usar de forma independiente. ¿Existe un combinador más eficiente que permita unaArray.prototype.reduce
?
Si observa la pila de llamadas, la declaración de retorno de la función reductoraacc => x => acc.concat([f(x)])
tendría que omitir varios marcos de pila. Este tipo de manipulación de pila me hace pensar en continuaciones. Quizás haya una manera eficiente de resolver este problema en Continuation Passing Style junto con una función call / cc adaptada, o al menos con un generador.