## fix by example

- 2021-03-11 -`fix`

is an interesting Haskell function that provides us with the ability to add recursion to non recursive functions.

It looks like this:

```
fix :: (a -> a) -> a
fix f = f (fix f)
```

In the function `fix`

, `f`

will get the result of `fix f`

as input, and will return some output of the same type.
`fix f`

represents another call to the function `f`

, which `f`

can call to recurse on itself.

Lets take a look at a few examples and use the substitution model to gain intuition on how this works.

#### id

Lets start by picking a function we can pass to fix. `id :: a -> a`

has a matching signature, lets try it:

```
λ> fix id
^CInterrupted.
```

What happened? ghci was busy trying to evaluate the function and didn't finish, so I had to cancel it. Why? Lets try to substitute ourselves:

```
ג> fix id
~> id (fix id) -- substitute fix with it's body
~> (\a -> a) (fix id) -- substitute id with it's body
~> fix id -- apply (fix id) as a in (\a -> a)
~> id (fix id) -- substitute fix with it's body
~> ...
```

As we can see we have an infinite loop of steps where we keep coming back to `fix id`

.
This is because `id`

always call `fix id`

as part of the computation and therefore recursing.

#### (+) 1

Let's take a look at another example with `(\x -> 1 + x) :: Int -> Int`

:

```
λ> fix (\x -> 1 + x)
*** Exception: stack overflow
```

Again, to understand what's going on - lets substitute:

```
ג> fix (\x -> 1 + x)
~> (\x -> 1 + x) (fix (\x -> 1 + x)) -- substitute fix with it's body
~> 1 + (fix (\x -> 1 + x)) -- apply
~> 1 + (\x -> 1 + x) (fix (\x -> 1 + x)) -- (+) and 1 are evaluated. we will evaluate the right hand side - the function call, by applying
~> 1 + (1 + (fix (\x -> 1 + x))) -- apply
~> ...
```

At each substitution of fix we add another step that needs to be done,
so we keep allocating new thunks without evaluating them and we use all of the stack space.
Here as well, we always use the argument `x`

that is passed to us, so we keep recursing.

We'll see more useful examples later.

### Non-Strict Semantics

One thing that we saw in previous examples is the evaluation order in Haskell. In a strict language, we first evaluate the arguments of a function, then we apply the arguments to the function's body, and then we evaluate the body of a function. But in Haskell, we evaluate computations only when we need to.

For example, take a look at the evaluation order of this function:

```
const :: a -> b -> a
const = \a -> \b -> a
```

Strict semantics:

```
ג> const (1 + 1) (2 + 2)
~> const 2 (2 + 2)
~> const 2 4
~> (\a -> \b -> a) 2 4
~> (\b -> 2) 4
~> 2
```

Notice how we evaluated `2 + 2`

without actually needing to do anything with it.

Non-strict semantics:

```
ג> const (1 + 1) (2 + 2)
~> (\a -> \b -> a) (1 + 1) (2 + 2)
~> (\b -> (1 + 1)) (2 + 2)
~> (1 + 1)
~> 2
```

Pretty cool how we didn't evaluate `(2 + 2)`

here, right?

This might sound silly, but what if `(2 + 2)`

is instead a very expensive computation,
or even one that never finished or throws an error? Non-strict semantics can help us
ignore computations we don't really need, and it can be useful in the case of `fix`

as we'll see next.

#### const 0

So let's take a look at another function with fix, this time we'll use `(\x -> const 0 x) :: a -> Int`

:

```
ג> fix (\x -> const 0 x)
~> (\x -> const 0 x) (fix (\x -> const 0 x))
~> const 0 (fix (\x -> const 0 x))
~> (\a -> \b -> a) 0 (fix (\x -> const 0 x))
~> (\b -> 0) (fix (\x -> const 0 x))
~> 0
```

Hey what do you know! Non-strict semantics helped us avoid the unnecessary recursion and let us terminate the evaluation of the expression.

This is interesting. Because the arguments to a function are not evaluated before entering a function,
the function can decide whether to evaluate the arguments or not (by using them, or not, like in the case of `const`

).
In our case with `const`

, it will always ignore the argument `x`

that is the recursion, so we really didn't use fix at all here.

#### factorial

Let's take a small leap and try to implement a `factorial :: Int -> Int`

function without a recursive call to itself by using `fix`

. Here we will sometimes call the recursion parameter passed to us from fix, and sometimes we won't.

```
factorial :: Int -> Int
factorial = fix impl
impl :: (Int -> Int) -> Int -> Int
impl recur n =
if n <= 1
then 1
else n * recur (n - 1)
```

The key idea when using `fix`

is that `a`

can represent any type, *including functions*.

It's important to remember that functions are first class in Haskell, when we see an `a`

,
it could also be some function and not just a regular value like `Bool`

.

So if we replace `a`

with `Int -> Int`

in the type signature for `fix`

,
we'll see that the function we pass to `fix`

should now be of type
`(Int -> Int) -> Int -> Int`

, and the resulted type of applying `fix`

to a function with that type would be `Int -> Int`

.

So for example, what is `fix impl`

? if we substitute `fix`

with its body, we get:
`impl (fix impl)`

, we know is that the first argument of `impl`

is the result of `fix impl :: Int -> Int`

,

which is a factorial function as we defined (and which we will evaluate only if we want to due to non-strict semantics), and the second argument should be the input to the function (the number for which we will calculate it's factorial).

Finally, let's evaluate this ourselves using the substitution model!

```
0 ג> factorial 3
1 ~> fix impl 3 -- substitute the body of factorial
2 ~> impl (fix impl) 3 -- substitute the body of fix
3 ~> (\recur -> \n -> if n <= 1 then 1 else n * recur (n - 1)) (fix impl) 3 -- substitute the body of impl
4 ~> (\n -> if n <= 1 then 1 else n * fix impl (n - 1)) 3 -- apply (fix impl)
5 ~> if 3 <= 1 then 1 else 3 * fix impl (3 - 1) -- apply 3
6 ~> if False then 1 else 3 * fix impl (3 - 1) -- apply 3 -- evaluate the if condition
7 ~> 3 * fix impl (3 - 1) -- choose the else branch
8 ~> 3 * impl (fix impl) (3 - 1) -- (*) and 3 are evaluated, let's evaluate fix
9 ~> 3 * (\recur -> \n -> if n <= 1 then 1 else n * recur (n - 1)) (fix impl) (3 - 1) -- substitute the body of impl
10 ~> 3 * (\n -> if n <= 1 then 1 else n * (fix impl) (n - 1)) (3 - 1) -- apply (fix impl)
11 ~> 3 * (if (3 - 1) <= 1 then 1 else (3 - 1) * (fix impl) ((3 - 1) - 1)) -- apply (3 - 1)
12 ~> 3 * (if 2 <= 1 then 1 else (3 - 1) * (fix impl) ((3 - 1) - 1)) -- evalute (3 - 1) in the if condition
13 ~> 3 * (if False then 1 else (3 - 1) * (fix impl) ((3 - 1) - 1)) -- evaluate the if condition
14 ~> 3 * ((3 - 1) * (fix impl) ((3 - 1) - 1)) -- choose the else branch
15 ~> 3 * ( 2 * (fix impl) ((3 - 1) - 1)) -- (*) is evaluated, now we evaluate the left hand side of (*)
16 ~> 3 * (2 * impl (fix impl) ((3 - 1) - 1)) -- and now the right side - starting with (fix impl)
17 ~> 3 * (2 * (\recur -> \n -> if n <= 1 then 1 else n * recur (n - 1)) (fix impl) ((3 - 1) - 1)) -- and now the right side - starting with (fix impl)
18 ~> 3 * (2 * (\n -> if n <= 1 then 1 else n * (fix impl) (n - 1)) ((3 - 1) - 1)) -- apply (fix impl)
19 ~> 3 * (2 * (if ((3 - 1) - 1) <= 1 then 1 else ((3 - 1) - 1) * (fix impl) ( ((3 - 1) - 1) - 1))) -- apply ((3 - 1) - 1)
20 ~> 3 * (2 * (if (2 - 1) <= 1 then 1 else ((3 - 1) - 1) * (fix impl) ( ((3 - 1) - 1) - 1))) -- evaluating the if condition...
21 ~> 3 * (2 * (if 1 <= 1 then 1 else ((3 - 1) - 1) * (fix impl) ( ((3 - 1) - 1) - 1))) -- still evaluating ...
22 ~> 3 * (2 * (if True then 1 else ((3 - 1) - 1) * (fix impl) ( ((3 - 1) - 1) - 1))) -- still...
23 ~> 3 * (2 * 1) -- choosing the true branch
24 ~> 3 * 2 -- evaluating
25 ~> 6 -- evaluating
```

Bam! It was pretty long, but we did it.

One step in particular that I think is worth noting is line 23, where we discard the recursion branch in favor of the terminating branch. We chose to end the recursion!

### Summary

We can use `fix`

to add recursion to a non recursive function by getting as an input argument the a function that represents the recursion part. And the magic behind the termination of `fix`

in Haskell resides with non-strict semantics.