如何实现更普遍降低功能允许提前退场？ [英] How to implement a more general reduce function to allow early exit?

问题描述

减少（又名与foldl 在FP）是在Javascript中最一般的迭代高阶函数。您可以实现，例如，地图或过滤而言减少。我用命令式循环更好地说明算法：

reduce (aka foldL in FP) is the most general iterative higher order function in Javascript. You can implement, for instance, map or filter in terms of reduce. I've used an imperative loop to better illustrate the algorithm:

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]

但是，你不能获得部分或每个从减少，因为两者都能够提前返回。

But you can't derive some or every from reduce, because both are able to return early.

那么，如何能在更广义的部分减少功能是什么样子？到现在为止，我想出了以下幼稚的做法：

So how can a even more generalized partial reduce function look like? Until now I've come up with following naive implementation:

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]

我也可以实施地图而言 foldLP ：

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]

的缺点是显而易见的：当不需要提前退出机制，总是不必要调用。转化和早期退出功能是由 foldLP 静态组成，不能独立使用。有没有更有效的组合子，使广义 Array.prototype.reduce ？

The drawback is obvious: Whenever an early exit mechanism isn't needed, always is invoked unnecessarily. The transforming and early exiting function are composed statically by foldLP and can't be used independently. Is there a more efficient combinator, that enables a generalized Array.prototype.reduce?

如果你看看调用堆栈，还原功能 ACC =＆gt;中return语句; X =＆GT; acc.concat（[F（X）]）将必须跳过几个堆栈帧。这种堆栈操作的让我觉得延续的。也许有解决继续与适于呼叫/ cc的函数传递样式沿着这个问题的有效方法。 - 或至少与发电机

If you look at the call stack, the return statement of the reducing function acc => x => acc.concat([f(x)]) would have to skip several stack-frames. This kind of stack manipulation makes me think of continuations. Maybe there is an efficient way to solve this problem in Continuation Passing Style along with an adapted call/cc function - or at least with a generator.

推荐答案

懒惰的评价平凡的解决这个问题。虽然我们没有在JavaScript中，我们可以通过传递一个函数，而不是一个值的效仿：

Lazy evaluation solves this trivially. While we don't have that in JavaScript, we can emulate it by passing a function instead of a value:

const foldR = f => acc => xs => xs.length
  ? f(xs[0])(() => foldR(f)(acc)(xs.slice(1)))
  : acc //   ^^^^^ "lazy"

const map = f => foldR(x => acc => [f(x)].concat(acc()))([])
const every = f => foldR(x => acc => f(x) && acc())(true)
//                                        ^^^^^^^^ short-circuited - f(x) ? acc() : false

let xs = [1, 2, 3, 4];
console.log(map(x => x+1)(xs)); // [2, 3, 4, 5]
console.log(every(x => x%2==0)(xs)); // false

另一种方法是使用CPS，在那里你可以很容易地跳转到函数的末尾：

An alternative would be to use CPS, where you can easily jump to the end of the function:

const foldL = f => acc => xs => cont => xs.length
  ? f(acc)(xs[0])(res => foldL(f)(res)(xs.slice(1))(cont))
  : cont(acc);

const map = f => foldL(acc => x => cont => f(x)(res => cont(acc.concat([res]))))([]);
//const every = f => // xs => cont =>
//            foldL(acc => x => c => f(x)(res => c(acc && res)))(true) // (xs)(cont)
//                                   ^^^^ eager call
const every = f => xs => cont =>
              foldL(acc => x => c => acc ? f(x)(c) : cont(false))(true)(xs)(cont)
//                 call only when acc=true ^^^^      ^^^^^^^^^^^ jump out early otherwise
let xs = [1, 2, 3, 4];
let inc = x => cont => cont(x+1);
map(inc)(xs)(console.log.bind(console)); // [2, 3, 4, 5]

let even = x => cont => cont(x%2==0)
every(even)(xs)(console.log.bind(console)); // false

这篇关于如何实现更普遍降低功能允许提前退场？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！