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 => yD 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)