javascript - JavaScript 中的 takeWhile 实现 - 寻找更好的想法

Question

Haskell 有一个 takeWhile 函数:

Prelude> takeWhile odd [1,3,5,7,8,9]
[1,3,5,7]

只要应用谓词函数结果为True，它就会从列表中“获取”元素。当它变为 False 时，它就会停止。

我们如何实现它？

这是我想出的 Haskell 递归方法:

takewhile::(a->Bool)->[a]->[a]
takewhile _ [] = []
takewhile f (x:xs) | f x == True = x : takewhile f xs
                   | otherwise = []

只要谓词 f x 为 True，它就会继续调用自身，否则它会返回一个空列表而不调用自身。

我可以想出以下 JavaScript 实现。它有点冗长，并调用定义另一个函数来传递中间结果:

function takeWhile(f, xs) {
 return take(f, xs, [])
}

function take(f, xs, arr) {
 if(!xs || xs.length === 0) {
 return arr
 }
 x = xs.shift()
 if(f(x)) {
   arr.push(x)
   return take(f, xs, arr)
 } else {
   return arr
 }
}

takeWhile((x)=>{
 return x % 2 !== 0
},[1,3,5,7,9,11])

是否有更好的想法在 JavaScript 中实现它？

Answer 1

如果您希望 takeWhile 像 HS 中那样执行，即延迟执行，则需要 JS 中的生成器:

function* takeWhile(fn, xs) {
    for (let x of xs)
        if (fn(x))
            yield x;
        else
            break;
}

function* naturalNumbers() {
    let n = 0;
    while (true)
        yield n++;
}

result = takeWhile(x => x < 10, naturalNumbers())
console.log([...result])

HS 代码的直接移植也是可能的，但它仅适用于物化数组(即急切):

// would be nice, but JS sucks ;(
// let takeWhile = (f, [x, ...xs]) => f(x) ? [x, ...takeWhile(f, xs)] : [];

let takeWhile = (f, xs) => xs.length ? takeWhileNotEmpty(f, xs) : [];
let takeWhileNotEmpty = (f, [x, ...xs]) =>  f(x) ? [x, ...takeWhile(f, xs)] : [];


let odd = x => x % 2
a = [1,3,5,7,8,9]
r = takeWhile(odd, a)
console.log(r)

实际上，正如 @naomik 所示 here有一个更好的方法来处理空列表:

let nil = {};
let takeWhile = (f, [x = nil, ...xs]) => (x === nil || !f(x)) 
    ? [] : [x, ...takeWhile(f, xs)];

console.log(takeWhile(x => x % 2, [1, 3, 5, 7, 8, 9]));

最后，您最初的尝试确实有道理，因为与上面不同的是，它是尾递归的，这是一件好事。可以更简洁地写为

let takeWhile = (f, xs) => take1(f, xs, []);
let take1 = (f, xs, acc) => xs.length ? take2(f, xs, acc) : acc;
let take2 = (f, [x, ...xs], acc) => f(x) ? take1(f, xs, acc.concat(x)) : acc;

两种方法的组合(即递归生成器)作为练习......