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)