Я использовал Y-combinator, используя динамику С#, а если нет, то что это?

Мой мозг, кажется, находится в мазохистском режиме, поэтому после утопления в this, this и this, он хотел пообщаться с некоторыми DIY на С#.

Я придумал следующее, что я не думаю, это Y-combinator, но, похоже, ему удается сделать нерекурсивную функцию рекурсивной, не ссылаясь на себя:

Func<Func<dynamic, dynamic>, Func<dynamic, dynamic>> Y = x => x(x);

Итак, учитывая эти:

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(self)(n - 1);
Func<dynamic, Func<dynamic, dynamic>> fib = 
                  self => n => n < 2 ? n : self(self)(n-1) + self(self)(n-2);

Мы можем сгенерировать их:

Func<dynamic, dynamic> Fact = Y(fact);
Func<dynamic, dynamic> Fib = Y(fib);

Enumerable.Range(0, 10)
          .ToList()
          .ForEach(i => Console.WriteLine("Fact({0})={1}", i, Fact(i)));

Enumerable.Range(0, 10)
          .ToList()
          .ForEach(i => Console.WriteLine("Fib({0})={1}", i, Fib(i)));

Ответы

Ответ 1

Нет, это не Y combinator; вы на полпути. Вам все равно нужно откорректировать самоприменение в рамках "семенных" функций, к которым вы его применяете. То есть вместо этого:

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(self)(n - 1);

у вас должно получиться следующее:

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(n - 1);

Обратите внимание на одно вхождение self во втором определении в отличие от двух вхождений в первом определении.

(отредактировано, чтобы добавить:) BTW, так как ваше использование С# имитирует лямбда-исчисление с оценкой по каждому значению, комбинатор с фиксированной запятой, который вы хотите, тот, который часто называется Z, а не Y

(снова отредактировано, чтобы уточнить:) Уравнение, описывающее Y, таково (см. страницу wikipedia для вывода):

Y g = g (Y g)

Но в большинстве практических языков программирования вы оцениваете аргумент функции перед вызовом функции. В сообществе языков программирования, которое называется оценкой по каждому значению (не следует путать с тем, как программисты C/С++/Fortran/etc различают "вызов по значению" и "вызов по ссылке", а "вызов путем копирования-восстановления", и т.д.).

Но если бы мы это сделали, мы получили бы

Y g = g (Y g) = g (g (Y g)) = g (g (g (Y g))) = ...

То есть мы потратили бы все свое время на построение рекурсивной функции и никогда не обходим ее применение.

При оценке по имени, с другой стороны, вы применяете функцию здесь g к выражению неоцененного аргумента, здесь (Y g). Но если g похоже на fact, он ждет другого аргумента, прежде чем он что-либо сделает. Поэтому мы ожидаем второй аргумент g, прежде чем пытаться оценить (Y g) далее --- и в зависимости от того, что делает функция (т.е. Если у нее есть базовый случай), нам может не понадобиться оценивать (Y g) вообще. Поэтому Y работает для оценки по имени.

Исправление для вызова по значению - это изменение уравнения. Вместо Y g = g (Y g) вместо этого мы хотим получить следующее выражение:

Z g = g (λx. (Z g) x)

(Я думаю, что я получил уравнение справа или близко справа. Вы можете вычислить его и посмотреть, соответствует ли оно определению Z.)

Один из способов думать об этом - вместо вычисления "всей рекурсивной функции" и передачи ее g, мы передаем ей функцию, которая будет вычислять рекурсивную функцию немного за раз - и только тогда, когда нам действительно нужно немного больше, чтобы мы могли применить его к аргументу (x).