Наверное все знают что в C# 3.0 лямбда выражения, которые позволяют записывать анонимные функции (то есть функции без имени).
Например:
seq.Select(x => x * x);
Выражение x => x*x является функцией одного аргумента и возвращает значение квадрата числа.
А теперь попробуем записать функцию факториала:
Func<int, int> f = x => x > 1 ? x * f(x - 1) : 1;
Компилятор C# такое выражение не компилирует. Ругается на неинициализированную переменную f в правой части. Кстати roslyn такое прожевывает нормально. Тем не менее код выше не является выражением, его нельзя передать параметром в функцию.
Попробуем превратить его в выражение.
fact = f => x => x > 1 ? x * f(x - 1) : 1;
Тип выражения справа получится Func<Func<int,int>, Func<int,int>>, параметром передается рекурсивный вызов, чтобы его сформировать надо снова подставить рекурсивный вызов в функцию. Получится что-то вроде бесконечного вызова
fact(fact(fact(fact(…. но реально число вызовов конечно.
Немного теории
Для функций f которая принимает аргумент и возвращают значения из одного и того же множества (на C# это записывается как Func<T,T>, а в математике T –> T) может существовать “неподвижная точка” x, для которой f(x) = x. Чтобы находить неподвижные точки можно построить комбинатор g:(T->T)->T, такой что g(f) = x и f(x) = x. Функция g называется комбинатором неподвижной точки.
В лямбда исчислении есть теоремы доказывающие существование неподвижных точек у некоторых функций и формулы комбинаторов. Не все формулы можно перенести в типизированные языки.
Краткая формула для рекурсивного комбинатора неподвижной точки Y выглядит как Y(g) = g(Y(g)). Если выполнить подстановку то получится g(g(Y(g))), выполняя подстановку бесконечное число раз получим как раз то что нам нужно для факториала.
Вернемся к практике
Попробуем написать на C#
static T Y<T>(Func<T, T> f) { return f(Y(f)); }
Но язык C# использует энергичные вычисления и Y-комбинатор сразу попытается посчитать бесконечную рекурсию. Что приведет к StackOverflowException.
Ленивость вычислений как всегда вводится через лямбды.
static Func<T, T> Y<T>(Func<Func<T, T>, Func<T, T>> f) { return x => f(Y(f))(x); }
После этого вполне можно написать следующий код:
var fact = Y<int>(f => x => x > 1 ? x * f(x - 1) : 1);
Или например
seq.Select(Y<int>(f => x => x > 1 ? x * f(x - 1) : 1));
Таким образом получили возможность записывать анонимную рекурсию в виде выражения.
Заключение
Знание фундаментальной теории очень помогает писать программы и зачастую дает возможность улучшить их крайне неожиданными способами. Изучение таких тем никогда не будет лишним багажом.
