Let’s do some math.

If we continuously do `cosine`

of 0 and keep on applying `cosine`

over the result, we end up in a number finally that gets `fixed`

forever. The number is 0.73908513321516067.

```
cos(cos(cos(cos(x))))
```

Ofcourse this example is a blatant copy from one of the most wonderful blogs ever written about fix-points in Scheme language - https://mvanier.livejournal.com/2897.html.

You can choose to read it. This blog is a mere adoption of the ideas presented in the blog, but in Scala language.

## Fix point being a function

So, yes, the fix-point of `cos`

is `x`

if `cos(x) = x`

. But a fix-point may not be always a real number. It could be even a `type`

. A `function`

is a `type`

indeed.

Sure what does that mean? Well if `fix-point`

of a function like `cos`

is a `real-number`

, and if you say that a `fix-point`

can be a `function`

itself, that means the following:

```
There exists a `function`, whose fix-point can be a `funtion` itself. Hmmmmm.
```

## Stop explaining. Show an example.

A factorial of a number 3 is 3 * 2 * 1. It’s implementation is as follows:

```
val factorial: Int => Int =
if (n == 0) 1 else n * factorial(n - 1)
n =>
```

Sure, that’s easy. But let’s say someone asked you to implement the same `factorial`

such that the name of the function shouldn’t come in the body. Why? I think, answering this `Why`

leads to applications that use `Fix Points`

.

So, I request you to consider it as a challenge and a first step towards the understanding of `Fix`

and `Recursion Schemes`

and its wonderful application level usages in various other talks/blogs.

Answering the question, well may be I can do

```
def factorial(f: Int => Int): Int => Int =
if (n == 0) 1 else n * f(n - 1)
n =>
```

Ah, sure, but that’s not a factorial.

Ofcourse, that’s not a factorial, so let’s call it as `almostFactorial`

.

```
def almostFactorial(f: Int => Int): Int => Int =
if (n == 0) 1 else n * f(n - 1)
n =>
```

Now we need to implement a sensible `factorial`

in terms of `almostFactorial`

. All of us know, the real factorial exists when the `f`

( now staying as an argument in `almostFactorial`

) is `almostFactorial`

itself.

i.e,

```
val factorial: Int => Int =
almostFactorial(almostFactorial(almostFactorial(.....)))
```

Well if you try to implement it, you will be writing it forever. Anyone who is not convinced yet, please try it out.

Fine, let’s take a different approach then.

```
val factorial0: Int => Int =
almostFactorial(identity)
```

```
factorial0(0) // returns 1 ==> works
factorial0(1) // doesn't work, coz identity(n - 1) == identity(1 - 1) == identity(0) == 0
```

So `factorial0`

works only for zero. That’s fine for now.

Let’s implement for factorial1.

```
=
val factorial1 // that works
almostFactorial(factorial0)
=
val factorial2 // that works too.
almostFactorial(factorial1)
=
val factorial2_ // that works too.
almostFactorial(almostFactorial(almostFactorial(identity)))
: Int => Int =
val factorialInfinity.............almostFactorial(.........))) // forever
almostFactorial(almostFactorial(almostFactorial
```

Ah, kind of making sense now. `factorialInfinity`

is a function, which is a fixpoint of `almostFactorial`

. Infact `factorialInfinitiy`

is our real `factorial`

implementation.

```
factorial = fix-point-of almostFactorial
```

Hmmm. I think its time to figure out what is this `fix-point-of`

. Is there a function called `fix-point-of`

that allows us to pass `almostFactorial`

and return a real `factorial`

. In other words, is there a function called `fix-point-of`

that takes a function and returns the fix-point of that function.

```
def fixPointOf(f: <someFn>): fixPointOf_SomeFn
```

This `fixPointOf`

is also called “y combinator”. The `Y`

combinator is the one that converts a function to its fix-point. However, before we call it as a combinator, let’s call it as a function, because, to be a combinator it needs to satisfy a few conditions that we will explain later.

So, let’s implement `y`

such that it can take a function and returns its fix-point

```
// val factorial = almostFactorial(factorial)
// implies the following:
// If we are building a function called toFixPoint that takes `fn` as an argument then,
// that means the following
// toFixPoint (fn: Fn) = fn(toFixPoint(fn))
// Rename toFixPoint as Y, we will see later why
// Y(fn: Fn) = fn (Y(fn))
```

The above pseudo-code in Scala is

```
// (A => A) => (A => A) is alligned to the signature of almostFactorial
def Y[A](f: (A => A) => (A => A)) = f(Y(f))
val factorial = Y(almostFactorial) // Stack overflow haha
```

Stack overflow is, when you call Y the following thing happens:

```
f(Y(f)) ==
f(f(f(f(f.......))))
```

In other words, it tries to compute the fix-point function for you and it never ends.

Lambda saves us from this stack overflow - in a surprising way.

```
def Y[A](f: (A => A) => (A => A)): A => A = f(Y(f)) // Stack unsafe
// same as
def Y[A](f: (A => A) => (A => A)): A => A = f(a => Y(f)(a)) // Stack safe
```

Now my factorial implementation is

```
val factorial = Y(almostFactorial)
// factorial(3) is 6
```

Now, that works. However, we could further improve things.

The `Y`

function that we defined (the function that takes another function and returns a fix-point function) has a restricted shape.

```
def Y[A](f: (A => A) => (A => A)): A => A = f(Y(f)) // Stack unsafe
```

`(A => A) => (A => A)`

is equivalent to `A => A`

in types. In other words.

The following will compile.

```
def Y[A](f: A => A): A = f(Y(f)) // Stack unsafe
val factorial = Y(almostFactorial)
```

However, it’s sort of fairly hacky to make our latest `Y`

stacksafe using our lambda technique. Try yourself if you are having a doubt. This is sort of solveable though. However, for the time being, we can keep the same original `Y`

as it is but with only a minor change. We can make the return type a `B`

instead of `A`

to allow more flexiblity.

In the case of `factorial`

which is `Int => Int`

, `B`

is `A`

itself.

```
def Y[A](f: (A => B) => (A => B)): A => B = f(a => Y(f)(a)) // Stack safe
val factorial = Y(almostFactorial)
```

## Is our `y`

a combinator - No!

To become a combinator, the implementation of `y`

shouldn’t have any free variables in it.

For example: The below lambda is a combinator, because you can replace `f`

with its implementation in all occurances of `f`

.

```
val f = (x: Int) => x + 1
```

However, our `y`

is not a combinator, the implementation `f(y(f))`

has a free variable, and that’s `y`

itself. An explicit recursion here made it not call as a combinator.

```
def y[A, B] = (f: (A => B) => (A => B)) => f(y(f))
```

Well let’s revisit our factorial, and try abstracting out recursion again, and call our function `partFactorial`

. You will see why we are not calling it as `almostFactorial`

later.

```
def partFactorial(f: Int => Int): Int => Int = n => if (n == 0) 1 else n * f(n - 1)
```

Our real factorial is when `f`

is partFactorial itself.

```
// Will not compile
// well partFactorial _ is of the type `Int => Int => Int => Int`.
// However, `partFactorial` method above accepts `Int => Int`
def factorial = partFactorial(partFactorial _)
```

Ok, let’s do a hack. We have Any in scala, and see how it goes.

```
def partFactorialv0(self: Any): Int => Int =
if (n == 0) 1 else n * self.asInstanceOf[Any => (Int => Int)](self)(n - 1)
n =>
def factorial(n: Int) = partFactorialv0(partFactorialv0 _)
// Works, factorial(3) == 6
```

Why did we do this? Well, let’s extract out our `almostFactorial`

discussed above from this implementation.

Repeating `almostFactorial`

here:

```
def almostFactorial(f: Int => Int): Int => Int =
if (n == 0) 1 else n * f(n-1)
n =>
```

```
def partFactorialv1(self: Any): Int => Int = {
val f = self.asInstanceOf[Any => (Int => Int)](self) // val f = self(self)
if (n == 0) 1 else n * f(n - 1) // almost n factorial
n =>
}
// Hmmm, almost there. But it could be written as:
def partFactorialv2(self: Any): Int => Int = {
val f = self.asInstanceOf[Any => (Int => Int)](self) // val f = self(self)
if (n == 0) 1 else n * f(n - 1) // almost n factorial
n =>
}
def partFactorialv3(self: Any): Int => Int = {
val selfSelf = self.asInstanceOf[Any => (Int => Int)](self) // val f = self(self)
almostFactorial(selfSelf) // almost n factorial
}
// stack safety issues come into picture here, hence factorialV3(4) will not work
def factorialV3 = partFactorialv3(partFactorialv3 _)
```

Sure, we kind of extracted/reused almostFactorial in our latest implementations. You might be wondering why we are we doing this long loop of refactoring. I agree, but I request you to keep your patience and read on.

All our implementations of factorial is `partFactorial*(partFactorial* _)`

. Let’s get rid of it and try having only one single function called `factorial`

. That means `partFactorial`

implementation will become part of the `factorial`

itself.

```
// This was our partFactorial
def partFactorialv4: Any => (Int => Int) = {
almostFactorial(self.asInstanceOf[Any => (Int => Int)](self)) // almostFactorial self self
(self: Any) =>
}
// Moved inside our factorial implementation now.
def factorialV4: Int => Int = {
val partFactorial =
almostFactorial(self.asInstanceOf[Any => (Int => Int)](self)) // almostFactorial self self
(self: Any) =>
partFactorial(partFactorial)
}
// Well, lets rename this partFactorial to x
def factorialV5: Int => Int = {
val x =
almostFactorial(self.asInstanceOf[Any => (Int => Int)](self)) // almostFactorial self self
(self: Any) =>
x(x)
}
// Let's apply our trick: Replace { val x: A = a; x(x) } with { ((x: A) => x(x))(a) }
def factorialV6: Int => Int = {
x(x))(
((x: Any => (Int => Int)) => almostFactorial(self.asInstanceOf[Any => (Int => Int)](self))
(self: Any) =>
)
}
// Just renaming self to x, and obviously it doesn't change the meaning of the program.
// At this stage, I really recommend you try this code compile in your IDE
// instead of reasoning it without a code, because languages are always complex in some way.
def factorialV7: Int => Int = {
x(x))(
((x: Any => (Int => Int)) => almostFactorial(x.asInstanceOf[Any => (Int => Int)](x))
(x: Any) =>
)
}
```

As functional programmers, we cannot allow `almostFactorial`

to be part of the implementation. Let’s abstract that out.

```
// It's no more factorial because we extracted out almostFactorial as `f`.
def makeRecursive(f: (Int => Int) => (Int => Int)) = {
x(x))(
((x: Any => (Int => Int)) => f(x.asInstanceOf[Any => (Int => Int)](x))
(x: Any) =>
)
}
def factorialV8 = makeRecursive(almostFactorial)
// Works? stack overflow again. But we will fix it later. Hold tight.
```

Before we fix the stack overflow error, let’s simply try to prove that makeRecursive is our `y`

(implemented above).

And why do we need to prove ? `makeRecursive`

is our real `y`

that is devoid of free variables. In other words, we are going to prove that there is a `combinator`

version of `def y(f) = f(y(f))`

```
// makeRecursive is renamed to yCombinator0
def yCombinator0(f: (Int => Int) => (Int => Int)) = {
x(x))(
((x: Any => (Int => Int)) => f(x.asInstanceOf[Any => (Int => Int)](x))
(x: Any) =>
)
}
def factorialV9 = yCombinator0(almostFactorial)
// Below code summarises the following:
// y f = (lambdaXfxx)((lambdaXfxx))
// where lambdaXfxx = (x: Any) => f(x.asInstanceOf[Any => (Int => Int)](x))
def yCombinator1 =
(f: (Int => Int) => (Int => Int)) => {
(f(x.asInstanceOf[Any => (Int => Int)](x))
(x: Any) =>
)(f(x.asInstanceOf[Any => (Int => Int)](x))
(x: Any) =>
)
}
// The final refactoring
def yCombinator2 =
(f: (Int => Int) => (Int => Int)) => {val lambdaXFxx = ((x: Any) => f(x.asInstanceOf[Any => (Int => Int)](x)))
f(lambdaXFxx(lambdaXFxx))
}
```

There lies the proof. Can you see that?

```
// `yCombinator1` says the following:
y f = (lambdaXfxx)((lambdaXfxx))
// `yCombinator2` says the following
f ((lambdaXfxx)((lambdaXfxx)))
y f = f (y f)
y f =
// Hence, we proved our `def yCombinator2(f) = <expr>` is same as `def y(f) = f(y(f))`
```

In summary, `yCombinator2`

is our real `y`

combinator

## Remove stack overflow from y combinator

May be we can apply the lambda technique we used before i.e,

```
val x: A => A = f(z) } is same as {val x : A => A = a => f(z)(a)}
{
```

All thats done here is, apply an extra lambbda, wherever possible.

```
// Stack safe
def yCombinator =
(f: (Int => Int) => (Int => Int)) => {val lambdaXFxx = ((x: Any) => f((y: Int) => x.asInstanceOf[Any => (Int => Int)](x)(y)))
f(lambdaXFxx(lambdaXFxx))
}
def factorial = yCombinator(almostFactorial) // Works !!
```

## Generalise y combinator

```
def y[A, B] =
(f: (A => B) => (A => B)) => {val lambdaXFxx = ((x: Any) => f((y: A) => x.asInstanceOf[Any => (A => B)](x)(y)))
f(lambdaXFxx(lambdaXFxx))
}
// In scala3, you can also write something like this if you want.
// It removes `Any`, but it doesn't really matter :D
def yScala3_v0[A, B] =
(f: (A => B) => (A => B)) => {val lambdaXFxx:[Z] => Z => (A => B) = ([Z] => (z: Z) => f((y: A) => z.asInstanceOf[Z => (A => B)](z)(y)))
f(lambdaXFxx(lambdaXFxx))
}
// Well, why do we need an asInstanceOf. If you think about it, the above code is equivalent to
def yScala3[A, B] =
(f: (A => B) => (A => B)) => {lazy val lambda:[Z] => Z => (A => B) = ([Z] => (z: Z) => f((y: A) => lambda(z)(y)))
f(lambda(lambda))
}
// I think I liked that one
def y[A, B] =
(f: (A => B) => (A => B)) => {lazy val lambda:[Z] => Z => (A => B) =
f((y: A) => lambda(z)(y)))
([Z] => (z: Z) => f(lambda(lambda))
}
def factorial = y(almostFactorial)
```

Ah! That was a long loop. I know, but not only you learned fix-points, you learned its implementation in scala through `y f = f (y f)`

and proved that there exists a combinator, that is devoid of free variables that can achieve the same result in both strict and lazy languages.

Thanks, and Well done for reading such a long blog. If you are interested to read explanations in `Lisp`

or `Scheme`

language, go on and read this: https://mvanier.livejournal.com/2897.html