J'essaie d'écrire une fonction qui implémente foldl en JavaScript. J'essaie d'utiliser la récursivité dans la fonction mais je ne peux pas l'implémenter.
var foldl = function(f, acc, array) {
if (array.length == 0) {
return acc;
} else {
return f(array[0], foldl(f, acc, array.slice(-1)));
}
}
console.log(foldl(function(x, y) {
return x + y
}, 0, [1, 2, 3]));
console.log(foldl(function(x,y){return x+y}, 0, [1,2,3]));
Message d'erreur ..
RangeError: Maximum call stack size exceeded
4 réponses
Votre défi, comme mentionné ci-dessus, est que vous renvoyez un tableau du dernier élément. Et vous retournez toujours un tableau du dernier élément.
Ce qui manque dans les réponses ci-dessus, c'est qu'elles ne sont bonnes que pour se replier vers la droite. Pour le bon cas, vous pouvez simplement utiliser .slice(1)
, et cela tirera tout après la tête. Pour le cas de pli gauche, vous devez spécifier jusqu'où vous devez aller .slice(0, arr.length - 1)
.
const foldr = (f, acc, arr) => {
if (!arr.length) {
return acc;
} else {
const head = arr[0];
const tail = arr.slice(1);
return foldr(f, f(acc, head), tail);
}
};
foldr((x, y) => x + y, 0, [1, 2, 3])// 6
const foldl = (f, acc, arr) => {
if (!arr.length) {
return acc;
} else {
const head = arr[arr.length - 1];
const tail = arr.slice(0, arr.length - 1);
return foldl(f, f(acc, head), tail);
}
};
foldl((x, y) => x + y, 0, [3, 2, 1]); // 6
Cette:
array.slice(-1)
Devrait être:
array.slice(1)
slice(-1)
renvoie le tableau contenant le dernier élément. Lorsque vous utilisez le premier élément du tableau, vous souhaitez le tableau sans cet élément à la place. slice(1)
renverra le tableau sans le premier élément.
Notez que foldl
et foldr
peuvent les deux être implémentés de manière à itérer à travers la liste d'entrée dans l'ordre de repos (de gauche à droite). Des indices négatifs maladroits ou le calcul de positions slice
précises ne sont pas nécessaires.
const Empty =
Symbol ()
const foldl = (f, acc, [ x = Empty, ...xs ]) =>
x === Empty
? acc
: foldl (f, f (acc, x), xs)
const foldr = (f, acc, [ x = Empty, ...xs ]) =>
x === Empty
? acc
: f (foldr (f, acc, xs), x)
const pair = (a,b) =>
`(${a} ${b})`
const data =
[ 1, 2, 3 ]
console.log (foldl (pair, 0, data))
// (((0 1) 2) 3)
console.log (foldr (pair, 0, data))
// (((0 3) 2) 1)
Vous pouvez utiliser xs[0]
et xs.slice(1)
si vous ne souhaitez pas utiliser l'affectation de déstructuration
const foldl = (f, acc, xs) =>
xs.length === 0
? acc
: foldl (f, f (acc, xs[0]), xs.slice (1))
const foldr = (f, acc, xs) =>
xs.length === 0
? acc
: f (foldr (f, acc, xs.slice (1)), xs [0])
const pair = (a,b) =>
`(${a} ${b})`
const data =
[ 1, 2, 3 ]
console.log (foldl (pair, 0, data))
// (((0 1) 2) 3)
console.log (foldr (pair, 0, data))
// (((0 3) 2) 1)
...xs
via une affectation de déstructuration utilisée dans la première solution et slice
utilisée dans la deuxième solution crée des valeurs intermédiaires et pourrait être un impact sur les performances si xs
est de taille considérable. Ci-dessous, une troisième solution qui évite cela
const foldl = (f, acc, xs, i = 0) =>
i >= xs.length
? acc
: foldl (f, f (acc, xs[i]), xs, i + 1)
const foldr = (f, acc, xs, i = 0) =>
i >= xs.length
? acc
: f (foldr (f, acc, xs, i + 1), xs [i])
const pair = (a,b) =>
`(${a} ${b})`
const data =
[ 1, 2, 3 ]
console.log (foldl (pair, 0, data))
// (((0 1) 2) 3)
console.log (foldr (pair, 0, data))
// (((0 3) 2) 1)
Au-dessus de nos foldl
et foldr
sont des remplacements presque parfaits pour les natifs Array.prototype.reduce
et Array.prototype.reduceRight
respectivement. En passant i
et xs
au rappel, nous nous rapprochons encore plus
const foldl = (f, acc, xs, i = 0) =>
i >= xs.length
? acc
: foldl (f, f (acc, xs[i], i, xs), xs, i + 1)
const foldr = (f, acc, xs, i = 0) =>
i >= xs.length
? acc
: f (foldr (f, acc, xs, i + 1), xs[i], i, xs)
const pair = (acc, value, i, self) =>
{
console.log (acc, value, i, self)
return acc + value
}
console.log (foldl (pair, 'a', [ 'b', 'c', 'd' ]))
// a b 0 [ b, c, d ]
// ab c 1 [ b, c, d ]
// abc d 2 [ b, c, d ]
// => abcd
console.log (foldr (pair, 'z', [ 'w', 'x', 'y' ]))
// z y 2 [ x, y, z ]
// zy x 1 [ x, y, z ]
// zyx w 0 [ x, y, z ]
// => zyxw
Enfin, reduce
et reduceRight
acceptent un argument context . Ceci est important si la fonction de pliage f
fait référence à this
. Si vous souhaitez prendre en charge un contexte configurable dans vos propres plis, c'est facile
const foldl = (f, acc, xs, context = null, i = 0) =>
i >= xs.length
? acc
: foldl ( f
, f.call (context, acc, xs[i], i, xs)
, xs
, context
, i + 1
)
const foldr = (f, acc, xs, context = null, i = 0) =>
i >= xs.length
? acc
: f.call ( context
, foldr (f, acc, xs, context, i + 1)
, xs[i]
, i
, xs
)
const obj =
{ a: 1, b: 2, c: 3, d: 4, e: 5 }
// some function that uses `this`
const picker = function (acc, key) {
return [ ...acc, { [key]: this[key] } ]
}
console.log (foldl (picker, [], [ 'b', 'd', 'e' ], obj))
// [ { b: 2 }, { d: 4 }, { e: 5 } ]
console.log (foldr (picker, [], [ 'b', 'd', 'e' ], obj))
// [ { e: 5 }, { d: 4 }, { b: 2 } ]
slice(-1)
retourne uniquement le dernier élément. Si vous voulez récapituler sur le tableau, utilisez plutôt slice(1)
, qui renverra tous les éléments sauf le premier:
var foldl = function(f, acc, array) {
if (array.length == 0) {
return acc;
} else {
return f(array[0], foldl(f, acc, array.slice(1)));
}
}
console.log(foldl(function(x, y) {
return x + y
}, 0, [1, 2, 3]));
Questions connexes
De nouvelles questions
javascript
Pour des questions concernant la programmation dans ECMAScript (JavaScript / JS) et ses divers dialectes / implémentations (hors ActionScript). Veuillez inclure toutes les balises pertinentes dans votre question; par exemple, [node.js], [jquery], [json], etc.