A while ago I came across a piece of functional JavaScript that looked almost deliberately unreadable. At first glance it was baffling. Stare at it a bit longer and it starts to feel like some kind of arcane manuscript. It had that unmistakable “look how functional I am” energy.
Still, unpacking code like that is actually pretty fun. And it also happens to be a great excuse to revisit some basic functional programming ideas—anonymous functions, higher-order functions, recursion, and eventually the trick behind writing recursive anonymous functions.
Let’s begin with the code itself.
Start with the simple version
This problem is as ordinary as it gets: scan an array, find a value, return its index, and if it isn’t there, return null. Time complexity is O(n).
The straightforward old-school version needs no introduction:
//正常的版本
function find (x, y) {
for ( let i = 0; i < x.length; i++ ) {
if ( x[i] == y ) return i;
}
return null;
}
let arr = [0,1,2,3,4,5]
console.log(find(arr, 2))
console.log(find(arr, 8))
Now compare that with a functional rewrite that tries very hard to avoid looking ordinary:
//函数式的版本
const find = ( f => f(f) ) ( f =>
(next => (x, y, i = 0) =>
( i >= x.length) ? null :
( x[i] == y ) ? i :
next(x, y, i+1))((...args) =>
(f(f))(...args)))
let arr = [0,1,2,3,4,5]
console.log(find(arr, 2))
console.log(find(arr, 8))
You can sort of see the original logic flickering inside it, but it has been folded into expressions, recursive calls, and nested functions. The if statements are gone, replaced by ternary expressions so everything can stay in expression form.
To make sense of that, we need a little groundwork.
A quick refresher on JavaScript arrow functions
Arrow functions were introduced in ECMAScript 2015. They are anonymous functions by nature, and the basic syntax looks like this:
``` (param1, param2, …, paramN) => { statements } (param1, param2, …, paramN) => expression // 等于 : => { return expression; }
// 只有一个参数时,括号才可以不加: (singleParam) => { statements } singleParam => { statements }
//如果没有参数,就一定要加括号: () => { statements } ```
A few examples:
var simple = a => a > 15 ? 15 : a;
simple(16); // 15
simple(10); // 10
let max = (a, b) => a > b ? a : b;
// Easy array filtering, mapping, ...
var arr = [5, 6, 13, 0, 1, 18, 23];
var sum = arr.reduce((a, b) => a + b); // 66
var even = arr.filter(v => v % 2 == 0); // [6, 0, 18]
var double = arr.map(v => v * 2); // [10, 12, 26, 0, 2, 36, 46]
None of that is especially scary.
But notice something: in the simple and max examples, the arrow function is assigned to a variable, so it effectively gains a name. In functional code, though, you often write a function at the exact moment you need it, especially when a function returns another function.
Take this example:
function MakePowerFn(power) {
return function PowerFn(base) {
return Math.pow(base, power);
}
}
power3 = MakePowerFn(3); //制造一个X的3次方的函数
power2 = MakePowerFn(2); //制造一个X的2次方的函数
console.log(power3(10)); //10的3次方 = 1000
console.log(power2(10)); //10的2次方 = 100
Inside MakePowerFn, the returned function doesn’t really need a name. It can just be:
function MakePowerFn(power) {
return function(base) {
return Math.pow(base, power);
}
}
With arrow functions, that becomes:
MakePowerFn = power => {
return base => {
return Math.pow(base, power);
}
}
And we can compress it further:
MakePowerFn = power => base => Math.pow(base, power)
Written with a few extra parentheses and line breaks, it may actually be easier to read:
MakePowerFn = (power) => (
(base) => (Math.pow(base, power))
)
That brings us to the more interesting question: if anonymous functions don’t have names, how do they recurse?
Recursion with anonymous functions
Functional programming tries to eliminate mutable state and avoid for and while loops. In that style, iteration is usually expressed as recursion instead.
Classic recursive code calls itself by name. A factorial function is the standard example:
function fact(n){
return n==0 ? 1 : n * fact(n-1);
};
result = fact(5);
So what happens when the function has no name?
The trick is simple, even if it feels a bit sneaky: pass the anonymous function as an argument to another function. Once it becomes a parameter, that parameter has a name, so the function can call itself through it.
For example:
function combinator(func) {
func(func);
}
That does feel like cheating, but let’s keep going. Written as an arrow function, it looks like this:
（func) => (func(func))
Now let’s reshape the factorial example so it no longer refers to fact by name:
function fact(func, n) {
return n==0 ? 1 : n * func(func, n-1);
}
fact(fact, 5); //输出120
Then convert that into an anonymous arrow-function version:
var fact = (func, n) => ( n==0 ? 1 : n * func(func, n-1) )
fact(fact, 5)
We still assigned it to fact, though. To make it fully anonymous, we want the function to receive itself and invoke itself immediately.
In other words, this function:
(func, n) => ( n==0 ? 1 : n * func(func, n-1) )
should be passed as an argument into this function:
(func, x) => func(func, x)
That gives us:
( (func, x) => func(func, x) ) ( //函数体
(func, n) => ( n==0 ? 1 : n * func(func, n-1) ), //第一个调用参数
5 //第二调用参数
);
A little twisty? Definitely. But this is the basic idea.
Using a higher-order function to package recursion
There’s still a rough edge in the version above: the anonymous recursive function hardcodes the way it receives itself as an argument. We can abstract that pattern using a higher-order function.
Here is a higher-order factorial builder:
HighOrderFact = function(func){
return function(n){
return n==0 ? 1 : n * func(func)(n-1);
};
};
What this does is straightforward in principle: it takes a function and returns its recursive version.
To use it:
fact = HighOrderFact(HighOrderFact);
fact(5);
Or in one shot:
HighOrderFact ( HighOrderFact ) ( 5 )
That works, but it’s not pleasant to call directly. So we can wrap the HighOrderFact ( HighOrderFact ) part inside another function and let users treat the result as a normal fact function:
fact = function ( hifunc ) {
return hifunc ( hifunc );
} (
//调用参数是一个函数
function (func) {
return function(n){
return n==0 ? 1 : n * func(func)(n-1);
};
}
);
fact(5); //于是我们就可以直接使用了
With arrow functions, it gets shorter:
fact = (highfunc => highfunc ( highfunc ) ) (
func => n => n==0 ? 1 : n * func(func)(n-1)
);
That is the final functional version of factorial.
Back to the array search example
Now return to the original search routine:
//正常的版本
function find (x, y) {
for ( let i = 0; i < x.length; i++ ) {
if ( x[i] == y ) return i;
}
return null;
}
First, remove the for loop and rewrite it as recursion:
function find (x, y, i=0) {
if ( i >= x.length ) return null;
if ( x[i] == y ) return i;
return find(x, y, i+1);
}
Then turn that into an anonymous version with explicit self-passing. The if statements are rewritten as ternary expressions so everything remains expression-based:
( (func, x, y, i) => func(func, x, y, i) ) ( //函数体
(func, x, y, i=0) => (
i >= x.length ? null :
x[i] == y ? i : func (func, x, y, i+1)
), //第一个调用参数
arr, //第二调用参数
2 //第三调用参数
)
Finally, introduce a higher-order function so the real arguments are no longer part of the recursive mechanism itself:
const find = ( highfunc => highfunc( highfunc ) ) (
func => (x, y, i = 0) => (
i >= x.length ? null :
x[i] == y ? i : func (func) (x, y, i+1)
)
);
And yes, if you want the full functional-programming swagger, you absolutely write it with const. That way the function looks gloriously immutable by birth.
There was also a more elaborate version that introduced yet another nested next function and even used variadic arguments. In theory, if your goal is to make the code look even more dazzling—or more outrageous—you can keep wrapping more layers around it.
At this point the source of that “showy” style should be fairly clear.
This isn’t just showing off
Jokes aside, there is a serious idea underneath all of this. Complex behavior—including recursion—can be described in a mathematical way using functions alone. None of this is new. These ideas go back to work from the 1930s associated with Alonzo Church and Haskell Curry.
What’s happening here belongs to the family of techniques around the Y combinator and fixed-point combinators. Even if you never write production code in this style, understanding it gives you a much better feel for how recursion, anonymous functions, and higher-order functions fit together.
And once you’ve seen the trick, that impossible-looking functional code stops looking like magic.