Combinators

6/24/2006 7:53:43 PM

Combinators

Eric Lippert writes about a limitation of generic delegates in that they cannot be used to build combinators — a function that takes a function and returns a function. With nongeneric delegate one can define a combinator as follows:

delegate D D(D d);

Eric then demonstrates some combinators from combinatory logic. I thought that there were better examples from lambda calculus. Here are definitions of some Church numerals in which we express any number n as a higher-order function that applies another function f n times.

D N0 = f => x => x;
D N1 = f => x => f(x)
D N2 = f => x => f(f(x))

Func<int,D> NGEN = i => i == 0 ?  N0 : SUCC( NGEN( i – 1) ) 

Below are some arithmetic and logical operations:

D SUCC = n => f => x => n(f(x))
D PLUS = m => n => f => x => m(f(n(f(x)))
D MULT = m => n => f => m(n(f))

D FALSE = x => y => y
D TRUE = x => y => x

D IF = c => x => y => c(x)(y)
D AND = p => q => p(q)(FALSE)
D OR = p => q => p(TRUE)(q)
D NOT = p => p(FALSE)(TRUE)

 

Comments

 

Navigation

Categories

About

Net Undocumented is a blog about the internals of .NET including Xamarin implementations. Other topics include managed and web languages (C#, C++, Javascript), computer science theory, software engineering and software entrepreneurship.

Social Media