## Monday, 12 January 2009

### Refactoring Towards the Y Combinator: Part 6

This is a multi-part series. Part 1. Part 2. Part 3. Part 4. Part 5. Part 6.

This is the final part of my series on the Y combinator. By the end of part 5, the bulk of the work was done. All I have to do today is generalize it, clean it up and make it look pretty. Here is the code from part 5:

```public class Solution09 : ISolution
{
public Factorial MakeFactorialFunction()
{
HigherOrderFunction<Factorial> algorithm = (Factorial f) =>
{
return (int x) =>
{
return x < 2 ? 1 : x * f(x - 1);
};
};

SelfApplicable<HigherOrderEvaluator<Factorial>> factorial = (SelfApplicable<HigherOrderEvaluator<Factorial>> self) =>
{
return (HigherOrderFunction<Factorial> alg) =>
{
return (int x) =>
{
return alg(self(self)(alg))(x);
};
};
};
return factorial(factorial)(algorithm);
}
}```

I claimed that the factorial function, as it is defined here, is a version of the Y combinator. Indeed if you take a look at it, you will see that it really doesn’t have anything to do with calculating factorials anymore – that code has long since been moved into the “algorithm” function. But the signature of the function still mentions factorials, specifically the Factorial delegate. To get my definition for the Y combinator into a more usable state, I can replace usages of the Factorial delegate with Func<int,int>. Later on, I’ll be able to define a generic version so it can even be used for functions that take and compute a double, or string, or whatever. However when I make this change, I still need to return a Factorial (because my test harness requires the MakeFactorialFunction method to return a Factorial delegate). To get around this I will use an earlier trick of returning a lambda that can be cast as a Factorial delegate:

```/// <summary>
/// Its possible to make a generic version of the Y combinator for application to functions that take 1 argument and return a value of the same type.
/// Unfortunately we cannot continue to use the Factorial delegate if we want to make this generic version.
/// We rename the functions to better represent their purpose (factorial becomes Y, algorithm becomes factorial).
/// We can't just return Y(Y)(factorial)(x) because that will return a Func<int,int> but this method is supposed to return a Factorial. Although
/// they are basically the same thing, a conversion cannot be made. Therefore I have to return a lambda that calls Y(Y)(factorial)(x).
/// </summary>
public class Solution10 : ISolution
{
public Factorial MakeFactorialFunction()
{
HigherOrderFunction<Func<int, int>> factorial = (Func<int, int> f) =>
{
return (int x) =>
{
return x < 2 ? 1 : x*f(x - 1);
};
};

SelfApplicable<HigherOrderEvaluator<Func<int, int>>> Y =
(SelfApplicable<HigherOrderEvaluator<Func<int, int>>> self) =>
{
return (HigherOrderFunction<Func<int, int>> alg) =>
{
return (int x) =>
{
return alg(self(self)(alg))(x);
};
};
};

return x =>
{
return Y(Y)(factorial)(x);
};
}
}```

I can now make Y generic by moving it into its own generic class:

```/// <summary>
/// Move Y into its own class.
/// </summary>
public class Solution11 : ISolution
{
public Factorial MakeFactorialFunction()
{
HigherOrderFunction<Func<int, int>> factorial = (Func<int, int> f) =>
{
return (int x) =>
{
return x < 2 ? 1 : x * f(x - 1);
};
};

return x =>
{
return YCombinator<int>.Y(YCombinator<int>.Y)(factorial)(x);
};
}

private static class YCombinator<T>
{
public static SelfApplicable<HigherOrderEvaluator<Func<T, T>>> Y =
(SelfApplicable<HigherOrderEvaluator<Func<T, T>>> self) =>
{
return (HigherOrderFunction<Func<T, T>> alg) =>
{
return (T x) =>
{
return alg(self(self)(alg))(x);
};
};
};
}
}```

There is some ugliness with calling Y on itself now, so I add a “ApplyY” helper to the YCombinator class to make this part easier. I let Resharper help me use a more terse syntax for the lambdas, and this is the result:

```public class YCombinator<T>
{
private static readonly SelfApplicable<HigherOrderEvaluator<Func<T, T>>> Y =
self => algorithm => t => algorithm(self(self)(algorithm))(t);

public static readonly HigherOrderEvaluator<Func<T, T>> ApplyY = Y(Y);

}```

I’ve avoided using the terse lambda syntax up until now because I think it would have made comprehending the individual steps more difficult. I can use ApplyY like this:

`return YCombinator<int>.ApplyY(factorial)(10);`

Here is my final implementation for this entire exercise, utilizing the above class:

```/// <summary>
/// This is the final implementation.
/// The Y combinator has been moved to a separate file.
/// The factorial algorithm has been pushed to a static member and condensed.
/// </summary>
public class Solution12 : ISolution
{
private static readonly HigherOrderFunction<Func<int, int>> factorial =
f => x => x < 2 ? 1 : x * f(x - 1);

public Factorial MakeFactorialFunction()
{
return x => YCombinator<int>.ApplyY(factorial)(x);
}

// Example of using Y without any need for the Factorial delegate:
public int CalculateFactorialOf10()
{
return YCombinator<int>.ApplyY(factorial)(10);
}

}```

Now lets test my implementation of the Y combinator by using it to calculate Fibonacci numbers:

```public static class Fibonacci
{
private static readonly HigherOrderFunction<Func<int, int>> fibonacci =
f => x => x < 3 ? 1 : f(x - 1) + f(x - 2);

public static int Calculate(int nthNumber)
{
return YCombinator<int>.ApplyY(fibonacci)(nthNumber);
}
}```

Its horribly inefficient, but it works:

`Console.WriteLine(Fibonacci.Calculate(10));`

>> 55

So there you have it: the Y combinator implemented in C#, derived via many gradual refactorings. This implementation still has some limitations. For example, it won’t support a recursive algorithm that takes two arguments. You could of course modify the Y combinator class to support this, but because of the strongly typed nature of C#, it seems very difficult to make a definition of Y that could be applied to an algorithm with ANY signature. If you are interested in exploring the code that I provided in this series, you can download it here.

I really enjoyed this exercise and I would definitely encourage other programmers that are weak at functional programming to have a go at it. If you really know this stuff and my clumsy explanations made you cringe, please leave a comment! If you were following along with the series and got lost or stuck at some point, again, please comment! Practice makes perfect, but some constructive criticism can really help too. Thanks!

1. Thank you for this series, it's really enjoyable
-fairweather

2. Really glad to hear it fairweather. Thanks for the comment!

3. This is a great series, and very nicely explained.

4. This comment has been removed by a blog administrator.

5. Very good writing! I actually got it this time.
No constructive critisism this time, sorry :)

6. This comment has been removed by a blog administrator.

7. This comment has been removed by a blog administrator.

8. // One-argument Y-Combinator Y fixed-point combinator.
public static Func Y(Func, Func> f)
{
return
t => // A function that...
f( // Calls the factorial creator, passing in...
Y(f) // The result of this same Y-combinator function call...
// (Here is where the recursion is introduced.)
)
(t); // And passes the argument into the work function.
}

[TestMethod]
public void TestMethodY()
{
Func fib = Y(f => n => n > 1 ? f(n - 1) + f(n - 2) : n);
Func fact = Y(f => n => n > 1 ? n*f(n - 1) : 1);
Console.WriteLine(fib(6)); // displays 8
Console.WriteLine(fact(6)); // displays 720
}