bene : studio is a global consultancy, helping startups, enterprises and HealthTech companies to have better product

# Fixed-Point Combinators in JavaScript

*At bene : studio we love knowledge sharing to help the community of professionals. With 10+ years and over 100 projects behind us, we have a vast amount of experience. This is why we have launched a knowledge base on our blog with regular updates of tutorials, best practices, and open source solutions.*

*These materials come from our internal workshops with our team of developers and engineers.*

**Our workshops are restarting!**

Join the FREE React Native workshop on November 04, and learn **to do React Native automated tests with bene : studio and guest presenter from Bitrise**

**Join the workshop and invite your peers as well! **For full details and registration visit the workshop page:

An introduction to **fixed-point combinators** and **lambda calculus **with** real-world JavaScript examples** showing their power and beauty.

### TL;DR

- Lambda calculus can give you a
**deeper level of understanding**of how functions work and how they relate. - Fixed-point combinators can help you to implement
**recursion**. - Learning new stuff makes you stronger and
**better as a software engineer**. - Scroll to the bottom for
**practical applications**.

## Fixed-Point Combinators

Fixed-point combinators are *higher-order functions* such that:

yf = f (yf)

for all `f`

where

is a combinator, **y**`f`

is function and

is *space**function application*. This expands as follows:

yf = f (yf)

= f (f (yf))

= f (f (f (yf)))

= ...

This expansion is *recursion*.

With the use of combinators we can define self-referencing anonymous functions avoiding the use of variables. Let’s see the most simple one!

## The U Combinator

The U combinator is the most simple fixed-point combinator.

U g := g gU = λg.(g g)

where λg. is *lambda abstraction,* which is the definition of an anonymous function that takes an argument `g`

and substitutes it into its expression.

### Example in JavaScript

Define the `U`

combinator in JavaScript ES6 with *arrow function*.

U = g => g(g)

In practice we want our recursions to halt so we can calculate something. With *currying* we can introduce a halting condition.

Let’s calculate factorial with the `U`

combinator.

fact = U(// g for self-referencing

g =>

x =>//curryingis for passing the halting condition

(x === 0)// halting condition

? 1// halt

: x * g(g)(x - 1)// recursion)fact(5) === 120// true

## The Y Combinator

### The Y Combinator in Lambda Calculus

*Haskell B. Curry* defined the Y combinator as follows.

Y := λf.(λx.f (x x)) (λx.f (x x))

The Y combinator could be used even in this form but we can simplify it.

Lets do *β-reduction.*

Y g := (λf.(λx.f (x x)) (λx.f (x x))) g

= (λx.g (x x)) (λx.g (x x))

= g ((λx.g (x x)) (λx.g (x x)))

= g (Y g)

The reduced form reveals that this is a fixed point combinator:

Y g = g (Y g)Y = λg.(g (Y g))

### The Y Combinator in JavaScript

The Y combinator works only in lazy languages such as Haskell. In non-lazy languages like JavaScript the intuitive implementation expands until *stack overflow* or never halts in case of *tail call optimization*.

Y = g => g(Y(g))// intuitive implementationY( a => a )// call the Y combinator with the unit function

Uncaught RangeError:Maximum call stack size exceeded

Solution: let’s define *laziness* in JavaScript: wrap `Y(g)`

in a zero-arity function.

Y =

g => g(() => Y(g))

This way we can avoid automatic expansion. Let’s calculate factorial with `Y`

.

fact = Y(

g =>// g for self-referencing

x =>// this curryed function is returned by g()// halting condition

(x === 0)// halt

? 1// recursion

: x * g()(x - 1))fact(5) === 120// true

The difference to the previous implementation is that there is no need to pass `g`

to `g()`

, it is already bound.

## The Z Combinator

### The Z Combinator in Lambda Calculus

Z := λg.(λx.g (λv.((x x)v))) (λx.g (λv.((x x)v)))

There is an extra `v`

*argument* and an extra *function application* which is not present in the case of Y combinator definition.

After *β-reduction* we got:

Z gv= g (Z g)vZ g = λ.v(g (Z g) v)Z = λv.(λg.(g (Z g) v))

### The Z Combinator in JavaScript

An extra `v`

parameter and *function application* to the Y combinator gives us the Z combinator.

Because of the extra parameter `v`

we do not need to construct a *lazy* recursion in JavaScript.

Z =

g =>v =>g(Z(g))(v)

Let’s define a function that sums up the numbers from a given whole number to an other one.

example series:5 6 7 8

sum:26

Define the sum function with the Z combinator:

// sum(from, to)sum = Z(

g =>// g for self-referencing

from=>

to=>

(from === to)// halting condition

? to// halt

: from + g(from + 1)(to)// step one and recurse)sum(5)(8) === 26// true

We can see that there is no extra *laziness* implemented because the function application is lazy in itself.

## The Connection Between U, Y and Z

Let us consider the JavaScript implementations.

U= g => g(g) //recursion is strict, must curryY= g => g(() => Y(g)) //we made the recursion 'lazy'Z= g =>v =>g(Z(g))(v)//explicit currying makes it 'lazy'

## Practical Examples in JavaScript

Here are some real-world examples using fixed point combinators.

### Accept Terms

We would like users to accept terms. Ask them until they accept it.

It can be done *without naming a function *for the recursion.

Y(ask=>

(prompt('Accept terms?') !== 'yes')

?ask()

: alert('Thanks!')

)

We can even count how many times a user did not accept terms.

Y(ask =>count =>

(prompt('Accept terms?') !== 'yes')

? ask()(count + 1)

: alert('At last! It took ' + count + ' times.')

)(1)

We can notice that counting is done via *currying*.

You can read more on Currying in JavaScript ES6.

### Fetch Retry

We can retry unsuccessful `fetch()`

or `XHR`

operations with a maximum number of attempts with manual operation on the UI.

Y(

retry =>

attempts =>

fetch('/betcha-cant-load-this')

.then(

res => res.ok

? alert('Loaded!')

: (

(attempts > 1 &&confirm('Reload?')) //retry on UI

? retry()(attempts - 1)

: alert('Could not load. '+ res.status)

)

)

)(5)

## Conclusion

I really believe that lambda calculus and functional programming can help software engineers to organize their thoughts in a consistent and rigorous way that helps writing good quality code.

Enjoy the world of combinators and functional JavaScript.

Feel free to comment and share your thoughts!

### See Also

Recursion with Combinators in JavaScript

## Did you like this? Join us!

Want to ask some questions? Share them with us via e-mail to partner@benestudio.co and we can set up a talk with our engineers.

Fancy working for the studio where you can work on international projects and write articles like this? Check out our open positions!

Looking for a partner for your next project? Check out our services page to see what we do and let’s set up a free consultation.