The comparison of these two code fragments makes perfect sense - as part of a tutorial. Functional programming is demanding and if the author doesn't confront his readers with the most efficient functional implementations, then to keep examples simple.
Why is functional programming demanding? Because it follows mathematical principles (and these don't always human logic) and because novices are accustomed to imperative style regularly. In FP the data flow has priority while the actual algorithms remain in the background. It takes time to get used to this style, but if you've done it once, you'll probably never look back!
How can you implement this example more efficiently in a functional way? There are several possibilities, of which I illustrate two. Note, that both implementations avoid intermediate arrays:
- Lazy Evaluation
Javascript is strictly evaluated. However, lazy evaluation can be emulated with thunks (nullary functions). Furthermore, foldR
(fold right) is required as iterative function from which filterN
is derived:
const foldR = rf => acc => xs => xs.length
? rf(xs[0])(() => foldR(rf)(acc)(xs.slice(1)))
: acc;
const filterN = pred => n => foldR(
x => acc => pred(x) && --n ? [x].concat(acc()) : n ? acc() : [x]
)([]);
const alpha = x => !x.match(/[0-9]/);
let xs = ["1", "a", "b", "2", "c", "d", "3", "e"];
filterN(alpha)(4)(xs); // ["a", "b", "c", "d"]
This implementation has the disadvantage that filterN
isn't pure, because it is stateful (n
).
- Continuation Passing Style
CPS enables a pure variant of filterN
:
const foldL = rf => acc => xs => xs.length
? rf(acc)(xs[0])(acc_ => foldL(rf)(acc_)(xs.slice(1)))
: acc;
const filterN = pred => n => foldL(
acc => x => cont => pred(x)
? acc.length + 1 < n ? cont(acc.concat(x)) : acc.concat(x)
: cont(acc)
)([]);
const alpha = x => !x.match(/[0-9]/);
let xs = ["1", "a", "b", "2", "c", "d", "3", "e"];
filterN(alpha)(4)(xs); // ["a", "b", "c", "d"]
It is a bit confusing how foldR
and foldL
differ. The difference is not in the commutativity but in the associativity. The CPS implementation has still a drawback. filterN
should be separated into filter
and takeN
, to increase code reusability.
- Transducers
Transducers allow to compose (reducing/transforming) functions, without having to rely on intermediate arrays. Consequently, we can separate filterN
into two different functions filter
and takeN
and thus increase their reusability. Unfortunately I haven't found a concise implementation of transducers that would be suitable for a comprehensible and executable example. I'll try to develop my own, simplified transducer solution and then give an appropriate example here.
Conclusion
As you can see, these implementations may not be as efficient as the imperative solution. Bergi has already pointed out that execution speed is not the most relevant concern of functional programming. If micro optimizations are important for you, you should continue to rely on imperative style.
reduce