takeWhile implementation in JavaScript - Looking for better ideas

Question

Haskell has a takeWhile function:

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

It “takes” elements from a list as long as applying the predicate function results in True. At the point it becomes False, it stops.

How can we implement it?

Here is a Haskell recursive approach I came up with:

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

It keeps on calling itself as long as predicate f x is True, otherwise it returns an empty list without calling itself.

I could come up with the following implementation for JavaScript. It is a bit verbose and invokes defining another function to pass the intermediate result around:

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

Are there better ideas for implementing it in JavaScript?

Answer 1

If you want your takeWhile to perform like in HS, i.e. lazily, you need generators in 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])

A straight port of the HS code is also possible, but it only works with materialized arrays (that is, eagerly):

// 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)

Actually, as @naomik shows here there's a better way to deal with empty lists:

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

Finally, your initial attempt does have a point, because, unlike the above, it's tail-recursive, which is a Good Thing. It can be written more concisely as

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;

A combination of both approaches (that is, a recursive generator) left as an exercise...

Answer 2

Here's a concise solution:

const takeWhile = (fn, arr) => {
  const [x, ...xs] = arr;

  if (arr.length > 0 && fn(x)) {
    return [x, ...takeWhile(fn, xs)]
  } else {
    return [];
  }
};

---

Here's an extra condensed version of the above:

const takeWhile = 
  (fn, a) => a.length && fn(a[0]) ? [a[0], ...takeWhile(fn, a.slice(1))] : [];

It's not easily readable, so I don't recommend you use the condensed version.

---

A tail recursive version:

const takeWhile = (fn, arr) => {
  const recur = (a, acc) => {
    const [x, ...xs] = a;

    if (a.length > 0 && fn(x)) {
      return recur(xs, [...acc, x]);
    } else {
      return acc;
    }
  }

  return recur(arr, []);
};