# Lambda Calculus via C# (3) Fundamentals - Function composition

[Obsolete] See latest version - [Lambda Calculus]

It may not be the best place to discuss function composition in the lambda calculus series. However, function composition will be used a lot in later articles, so here is a brief introduction.

# Function composition

Function composition means to combine simple functions into a more complicated function. The composition of f1 and f2 is defined as: f2 ∘ f1. This new function’s application is:

(f2 ∘ f1) x := f2 (f1 x)

Here the function names f1 and f2 imply the order of being applied. f2 ∘ f1 can also be read as f2 after f1.

Again, it is perfectly nature normal thing to chain 2 function application together, by using the first function’s output as the second function’s input:

double x = 1; double y = Math.Sqrt(Math.Abs(x));

The following is a more complicated function, combined by 2 simple functions:

Func<double, double> absAndSqrt = x => Math.Sqrt(Math.Abs(x));

So absAndSqrt is a composition of Math.Abs and Math.Sqrt.

Generally, a function of type Func<T1, T2> and a function of type Func<T2, T3> can be composed to a new function of type Func<T1, T3>:

public static partial class FuncExtensions { public static Func<T1, T3> o<T1, T2, T3> (this Func<T2, T3> function2, Func<T1, T2> function1) => arg => function2(function1(arg)); }

Unfortunately, in C# there is no place to define custom function operators, so extension method has to be used. This method is named o to mimic the ∘ operator. Also, in lambda calculus, functions are curried, so this one extension method is good enough.

## Built-in operator in other languages

It is common for other functional language to have a built in function composition operator. In Haskell, ∘ is just dot (.):

(.) :: (b -> c) -> (a -> b) -> a -> c f2 . f1 = \x -> f2 (f1 x)

And F# has >>:

let inline (>>) f1 f2 x = f2 (f1 x)

It is called forward composition. So there is also a backward composition operator <<:

let inline (<<) f2 f1 x = f2 (f1 x)

# Properties

Function composition has 2 important properties

## Associativity

Function composition is associative. That means (f3 ∘ f2) ∘ f1 and f3 ∘ (f2 ∘ f1) are the same.

When applying x to (f3 ∘ f2) ∘ f1, according to the definition of ∘:

((f3 ∘ f2) ∘ f1) (x) ≡ (f3 ∘ f2) (f1 (x)) ≡ f3 (f2 (f1 (x)))

And when applying x to f3 ∘ (f2 ∘ f1):

f3 ∘ (f2 ∘ f1) ≡ f3 ∘ (f2 (f1 (x))) ≡ f3 (f2 (f1 (x)))

So they lead to identical result. In C#, this means f3.o(f2).o(f1) and f3.o(f2.o(f1)) are the same.

## Unit

There is a unit function for function composition:

`Id := λx.x`

so that:

`f ∘ Id ≡ f`

and

`Id ∘ f ≡ f`

In C#, Id is:

public static partial class FuncExtensions { public static T Id<T> (T value) => value; }