在 Javascript 中实现 Foldl 功能

Question

我正在尝试编写一个在 JavaScript 中实现 foldl 的函数。我正在尝试在函数中使用递归但无法实现它。

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]));

错误信息..

 RangeError: Maximum call stack size exceeded

Answer 1

这个：

array.slice(-1)

应该是：

array.slice(1)

slice(-1) returns 包含最后一个元素的数组。当您使用数组的第一个元素时，您希望数组不包含该元素。 slice(1) 将 return 没有第一个元素的数组。

Answer 2

slice(-1) return 只有最后一个元素。如果要递归数组，请改用 slice(1)，这将 return 除第一个元素之外的所有元素：

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]));

Answer 3

如上所述，您面临的挑战是要返回最后一个元素的数组。而且你总是返回最后一个元素的数组。

上面的答案中缺少的是它们只适合向右弃牌。对于正确的情况，您可以只使用 .slice(1)，这将把所有内容都拉到头部之后。对于 fold left 的情况，你需要指定你需要走多远 .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

Answer 4

请注意 foldl 和 foldr 可以 both 以先到先得的方式遍历输入列表的方式实现（左-向右）顺序。不需要笨拙的负索引或计算精确的 slice 位置。

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)

如果你不想使用解构赋值，你可以使用xs[0]和xs.slice(1)

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 通过第一个解决方案中使用的解构分配和第二个解决方案中使用的 slice 创建中间值，如果 xs 相当大，则可能会影响性能。下面是避免这种情况的第三种解决方案

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)

我们的 foldl 和 foldr 分别是本地人 Array.prototype.reduce 和 Array.prototype.reduceRight 的几乎完美的替代品。通过将 i 和 xs 传递给回调，我们更接近

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

最后，reduce 和 reduceRight 接受一个 context 参数。如果折叠函数 f 引用 this，这一点很重要。如果你想在自己的折叠中支持可配置的上下文，这很容易

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 } ]

在 Javascript 中实现 Foldl 功能

Implement Foldl function in Javascript

javascript

recursion

functional-programming

fold