Y-combinator in C#

bleyman

Собственно, вот.

using System;  

  

namespace TestTC  

{  

	class TestYCombinator2  

	{  

		public delegate R Func<P, R>(P p);  

  

		public delegate int Fii(int i);  

  

		public delegate Fii Branch(Branch p);  

  

  

		public static int testY  

		{  

			return new Func<Func<Fii, Fii>, Fii>(delegate(Func<Fii, Fii> f)  

			{  

				return new Branch(delegate(Branch x)  

				{  

					return f(delegate(int y)  

					{  

						return x(xy);  

					});  

				}delegate(Branch x)  

				{  

					return f(delegate(int y)  

					{  

						return x(xy);  

					});  

				});  

			})  

			(delegate(Fii f)  

			{  

				return delegate(int i)  

				{  

					return (i <= 0) ? 1 : i * f(i - 1);  

				};  

			}6);  

		}  

  

		public static void Main(string[] args)  

		{  

			Console.WriteLine(testY;  

		}  

	}  

}  

Забавно, по-моему. Написано по мотивам жавакода тут http://dtm.livejournal.com/36832.html
Да, забавность я вижу в том, что мне всегда казалось, что система типов в шарпе (и жаве, и вообще) достаточно проста и не позволяет делать типизированного лямбда-исчисления. А вот позволяет, оказывается, за счёт того, что можно объявить
public delegate Fii Branch(Branch p);
или, например,
public class Branch
{
public abstract Fii Apply(Branch b);
}
где формально получается рекурсивный тип — мы ещё не успели определить класс (или делегат а уже разрешаем получать его как параметр. В С такое невозможно, пришлось бы делать тайпкасты. Вот так-то!

Alexander08

а я не понял в отличии от поставивших плюсы. можно немного более подробно, пожалуйста?

smit1

>мы ещё не успели определить класс (или делегат а уже разрешаем получать его как параметр. В С такое невозможно, пришлось бы делать тайпкасты. Вот так-то!

class Magic

{

  void f(Magic& m);

  void g(Magic* m);

  void h(Magic m);

};

Я, наверно, просто не понял всю глубину мысли афтара

bleyman

В С такое невозможно! Не в плюсах, в С!
Буривуху: в каком статически типизированном языке лучше? Не считая хаскеля =)
Я не буду спорить, что на питоне это пишется гораздо проще, но тут меня в основном удивляет то, что получается полностью type-safe штука. Если подумать, то довольно очевидно, что система типов должна быть такой мощной, но для меня оказалось довольно неожиданным.
Батату, читай: http://en.wikipedia.org/wiki/Fixed_point_combinator#Y_combin...

tipnote

Да не, я не претензии выражаю. Просто отвык уже

Alexander08

public delegate Fii Branch(Branch p);

я тут еще наткнулся на применение этого синтаксиса(вроде в этом треде не было) - анонимная рекурсия.
на примере вычисления Фибоначчи

 

 delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);

 Recursive<int, int> fibRec = f => n => n > 1 ? f(fn - 1) + f(fn - 2) : n;

 Func<int, int> fib = fibRec(fibRec);

 Console.WriteLine(fib(6;

 

подробнее почитать тут http://rsdn.ru/article/dotnet/cslambda.xml (там еще много интересного) и тут http://blogs.msdn.com/wesdyer/archive/2007/02/02/anonymous-r...