Определение альтернативного Y комбинатора
В последнее время я провел некоторое время, оборачиваясь вокруг комбинатора Y, и обнаружил, что он обычно определяется (более или менее) следующим образом (это в C#, но язык выбора не важен):
public delegate TResult SelfApplicable<TResult>(SelfApplicable<TResult> r);
public static TResult U<TResult>(SelfApplicable<TResult> r)
{
return r(r);
}
public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f)
{
return U<Func<TArg1, TReturn>>(r => arg1 => f(U(r))(arg1));
}
Хотя это совершенно функционально (каламбур), мне кажется, что мое определение намного проще:
public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f)
{
return f(n => Y(f)(n));
}
Есть ли причина, по которой последнее определение не так распространено (я еще не нашел его в сети)? Возможно, это как-то связано с определением Y в терминах самого себя?
3 ответа
Анонимная рекурсия, то есть с помощью комбинатора с фиксированной запятой, не часто встречается в императивных, строго типизированных языках по той простой причине, что проще назвать вашу [цензурированную] функцию, чем определить анонимную функцию, которая выполняет ту же задачу. Кроме того, OOA&D учит нас, что код, который имеет значение в нескольких местах, не должен дублироваться; это должно быть названо и таким образом доступным из общего места. Лямбды по своей природе одноразовые; способ указания нескольких строк очень специфичного для конкретной ситуации кода для использования в более общем алгоритме, таком как циклические конструкции. Большинство рекурсивных алгоритмов - это вещи, которые имеют довольно общее применение (сортировка, генерация рекурсивных рядов и т. Д.), Что обычно приводит к тому, что вы делаете их более доступными.
Помимо лямбда-исчисления, в большинстве языков программирования анонимная функция F должна существовать, прежде чем ее можно будет использовать. Это исключает определение функции в терминах самой себя. В некоторых функциональных языках, таких как Erlang, функция F определяется с использованием "перегрузок", где более простые функции используются в качестве базовых вариантов для более сложных:
Fact(0) -> 1
Fact(i) -> Fact(i-1) * i
Это было бы хорошо, за исключением того, что в мире Erlang это теперь именованная функция "Fact", и при вызове этого метода программа будет "падать" через перегрузки, пока не найдет первый, для которого соответствуют параметры. В C# нет эквивалента этой точной конструкции, потому что C# не поддерживает выбор перегрузки на основе значения.
Хитрость заключается в том, чтобы каким-то образом получить ссылку на функцию, которую можно передать этой функции. Есть много способов, каждый из которых требует уже существующей ссылки. Если вы не можете обратиться к функции по имени, тогда тип функции FP-комбинатора Func<Func<Func<Func<Func<..., Метод Конрада является самым простым, но в C# он заканчивается своего рода хаком (он компилируется, но ReSharper по-прежнему жалуется, что это возможное InvalidOperationException; не может вызвать нулевой указатель метода).
Вот что я использую для простых случаев, в основном использую обходной путь делегата для неспособности неявно ввести неявно типизированную лямбду:
public static class YCombinator
{
public delegate TOut RLambda<TIn, TOut>(RLambda<TIn, TOut> rLambda, TIn a);
public static Func<T,T> Curry<T>(this RLambda<T,T> rLambda)
{
return a => rLambda(rLambda, a);
}
}
//usage
var curriedLambda = YCombinator.Curry<int>((f, i) => i <= 0 ? 1 : f(f, i - 1)*i)
var shouldBe120 = curriedLambda(5);
Вы можете объявить Curry<TIn, TOut> перегрузка для обработки случаев, когда тип ввода не является типом вывода, например, создание списка первых N простых чисел; эта функция P может быть рекурсивно определена как функция, которая создает список всех натуральных чисел, которые не делятся ни на одно меньшее простое число. Фиксированная точка P(1) => 2 определяет базовый случай, из которого можно определить рекурсивный алгоритм (хотя и не очень эффективный):
var curriedLambda =
YCombinator.Curry<int, List<int>>(
(p, i) => i == 1
? new List<int>{2}
: p(p, i - 1)
.Concat(new[]
{
Enumerable.Range(p(p, i - 1)[i - 2],
int.MaxValue - p(p, i - 1)[i - 2])
.First(x => p(p, i - 1).All(y => x%y != 0))
}).ToList()
);
Assert.AreEqual(new []{2,3,5,7,11}, curriedLambda(5));
И, таким образом, головоломка представляет себя; хотя вы, безусловно, МОЖЕТЕ определить все как функцию более высокого порядка, этот первичный искатель будет НАМНОГО быстрее, если будет определен императивно, а не функционально. Основное ускорение - это просто определение p(p,i-1) на каждом уровне, поэтому оно не оценивается 3 раза за уровень рекурсии. Умный язык, предназначенный для функциональной работы, сделает это за вас.
Я не уверен, что ваш вопрос, но я предполагаю, что причина, по которой ни Y-комбинатор, ни ваше решение не встречаются в дикой природе, двояка:
анонимные рекурсивные функции действительно редки; в частности, поскольку C# не имеет большой (читай: вообще никакой) поддержки хвостовой рекурсии.
Существует намного более простой (более читабельный для непосвященных) способ определения псевдо-"анонимных" рекурсивных лямбд в C#:
Func<int, int> fac = null; fac = x => x == 0 ? 1 : fac(x - 1) * x;Конечно, это не анонимно, но "достаточно близко" для практических целей.
Haskell Curry изобрел Y-комбинатор для определения и использования анонимных рекурсивных функций в нетипизированном лямбда-исчислении, определяемом следующим образом: Y = λf·(λx·f (x x)) (λx·f (x x))
Мое определение опровергает первоначальную цель Y-комбинатора, поскольку оно опирается на присущую C# поддержку определения рекурсивных функций. Однако он все еще полезен тем, что позволяет определять анонимные рекурсивные функции в C#.