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

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;
}```