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
0
Lucy 15 avril 2018 à 05:42

4 réponses

Meilleure réponse

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
1
Norguard 15 avril 2018 à 02:56

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.

1
fgb 15 avril 2018 à 02:47

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 } ]
0
Thank you 15 avril 2018 à 04:26

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]));
0
CertainPerformance 15 avril 2018 à 02:50