## Introduction

In my previous post Better Functional Programming Support Is Coming In C# 7 I argued that by the time you get a chance to write in C# 7 you should already be familiar with Functional Programming paradigm. But since you cannot use C# 7 at the time of writing – you should definitely consider F# for learning the concepts of Functional Programming. I hope we’ll be able to write elegant declarative-style code in C# as we do in F#.

It is hard to convince somebody to spend their time on something new without showing immediate benefits. But the benefits usually come in the form of idiomatic language features which can be overwhelming at first. I hope this post will show you immediate benefits of Functional Programming by looking at real code example and understanding the features one-by-one. I do not intend to present all of the features of F# – just enough to get you interested in Functional Programming.

Recently I have been watching Pluralsight course F# Fundamentals by Liam McLennan and stumbled upon this elegantly crafted code (fast forward to 0:46):

let rec quicksort = function
| [] -> []
| x :: xs ->
let smaller = List.filter ((>) x) xs
let larger = List.filter ((<=) x) xs
quicksort smaller @ [x] @ quicksort larger

I was just amazed how much functionality was packed into these 6 lines of code! If you are new to Functional Programming and F# in particular, it could be hard to appreciate this code, so let’s review feature-by-feature what makes this piece of code so elegant and powerful.

If you are curious to see how quicksort implementation looks in C# – scroll to the bottom of the post.

For the sake of clarity and simplicity, I will cover only features that pertain to the above mentioned code, intentionally omitting some features. For example, when I say, “in F# values are immutable”, I omit the fact that they are immutable by default, but you can use **mutable** modifier or reference cells. etc.

## Functional Language

For a language to be considered “functional,” it typically needs to support a few key features:

- Immutable data
- Ability to compose functions
- Functions can be treated as data
- Pattern matching
- Lazy evaluation

In this post we take a quick look at the first four features.

## Let Binding

If F# there are no variables. You define a value and assign a name (an identifier) to it and the same time. After that you are not allowed to assign a new value to that name.

To create a value you use a *let binding* via the **let** keyword

let x = 1
val x : int = 1

This above line created an immutable identifier **x** with a value of 1. Moreover, the F# type inference system figured out that the value of **x** is of type **int**.

F# treats functions as data whose value is the body of the function. To create a function use a *let binding* as well

let square x = x * x
val square : x:int -> int

There is no **return** keyword in F#. The result of the function is the last evaluated expression.

Notice the arrow in the signature of the function, which says “it is a function, that takes a single value **x** of type **int** and returns a value of type **int**“. Again, it is the F# type inference system who figured out that the input and output values of the function are going to have a type of **int**.

If the function has more than one parameter we separate them with space

let add x y = x + y
val add : x:int -> y:int -> int

Notice two arrows in the signature of the function, which says “it is a function, that takes two values – **x** and **y** of type **int** and returns a value of type **int**“.

But to be more correct, it rather says “it is a function, that takes a value **x** of type **int** and returns a function that takes a value **y** of type **int** and returns a value of type **int**“. Confused yet? Read on!

## Understanding Function Signature

When you look at the signature (not definition!) of the function, treat each arrow as a separate function with its input on the left and output on the right.

So, when you see typeA **->** typeB, think of it as a function, that takes an input value of typeA and produces a value of typeB.

Similarly, when you see typeA **->** typeB **->** typeC, you count arrows and mentally create two functions from right to left thinking: typeB **->** typeC is a function that takes an input of typeB and produces a value of typeC. You can name this function as f2. And then, typeA **->** typeB, is a function, that takes an input of typeA and produces a value of typeB.You can name this function as f1. So, you get f1 -> f2. You can stitch these two functions together because the output of the first one is of the same type as the input of the second one.

## Function Application

In F# instead of saying “I **call** a function f with arguments x and y” you rather say “I **apply **a function f to arguments x and y”.

So, here we are applying function **square** to value **3** of type **int**

let squareResult = square 2
val squareResult : int = 4

As you see, the result of application of function square to its argument is a value of type int.

And here we are applying function **add** to values **3** and **5**, which are both of type **int**

let addResult = add 3 5
val addResult : int = 8

Again, the result of application of function add to its arguments is a value of type int.

## Partial Function Application

What happens when you apply your function and do not specify all of its arguments? In other words – you apply a function to a partial set of its arguments? In imperative languages you will get an error, but in F# you will get a partially applied function.

Let’s see what we get when we apply function add to its first argument only:

let addThreeTo = add 3
val addThreeTo : (int -> int)

Have you noticed an arrow? It’s a function! It has a slightly different signature – it has parentheses around it, but it is still a function.

So, **addThreeTo** is a partially applied function **add** with the value **3** “baked in” for its first parameter into it. Looking at the signature we see that it is a **function**, that takes one parameter of type **int** and returns value of type **int**. And since it is a function – we can apply it to other arguments!

addThreeTo 1
val it : int = 4

You can clearly see, that the result of application of a partially applied function to its argument is just a regular value of type **int**.

## Anonymous Function / Lambda Expression

Previously, when we defined a body of the function, we bounded it to an identifier so that we could use it later. But if we want to bundle code together for local application only and either do not plan to re-use it later or do not want to pollute the namespace – we can use anonymous functions, also known as lambda expressions, to create a function inline.

To create lambda expression you use the **fun** keyword, followed by the function’s parameters and an arrow. So, instead of our **square** and **add** functions we could have used the following two lambda expressions:

(fun x -> x * x) 2
val it : int = 4

and

(fun x y -> x + y) 3 5
val it : int = 8

## Higher-Order Functions

Because in F# a function is just a value, other functions, called higher-order functions, can takes functions as parameters and treat them as return value.

Let’s say we want to have a function that will apply different algorithms to two values. And we do not know what that algorithm would be, we just know that it takes two values. So, the parameter **f** would be a function (an algorithm) that we would apply to parameters **x** and **y**. Let’s use lambda expressions to specify different algorithms

let applyAlgorithm f x y = f x y
applyAlgorithm (fun x y -> x + y) 3 5
val it : int = 8
applyAlgorithm (fun x y -> x * y) 3 5
val it : int = 15

How about some fun! What if we want to partially apply the algorithm to its first argument? Mind-bending, but piece of cake in F#!

let multiplyByThree = applyAlgorithm (fun x y -> x * y) 3
multiplyByThree 5
val it : int = 15
multiplyByThree 6
val it : int = 18
multiplyByThree 7
val it : int = 21

## F# Syntactic Sugar

If the lambda expression has only one parameter and it is being used as the last argument in the body, you can omit **fun** keyword, **arrow**, **parameter** and the **argument**itself.

let formatOutput f x = f x
formatOutput (fun x -> sprintf "The value is %d" x) 5
formatOutput (sprintf "The value is %d") 5
val it : string = "The value is 5"

## Symbolic Operators

When you apply a function, you use so-called **postfix** notation, meaning that the arguments you apply the function to follow the name of the function

add 1 2

But using postfix notation expressing some mathematical formulae would be pretty difficult to read

(mult (add 1 2) (add 3 4))

For these purposes you can create a symbolic operator – a function, whose name is made out of any sequence of the following symbols: **!%&*+-./@^|?**

In the function definition you need to place these symbols in the parentheses

let (@%@) x y = x + y
val ( @%@ ) : x:int -> y:int -> int

By default, when you apply symbolic operator to its arguments you use **infix** notation, meaning that you place the first argument before the symbolic operator and the second – after it.

3 @%@ 4
val it : int = 7

If you want to use postfix notation when applying symbolic operator – put parentheses around it

(@%@) 3 4
val it : int = 7

You use postfix notation with symbolic operators in case if you want to partially apply it to the argument

let partiallyAppliedSymbolicOperator = (@%@) 3
val partiallyAppliedSymbolicOperator : (int -> int)
partiallyAppliedSymbolicOperator 4
val it : int = 7

## Recursive functions

To define a function that can call itself use **rec** keyword

let rec factorial n =
if n < 0 then
failwith "The value n cannot be negative"
elif n <= 1 then
1
else
n * factorial (n - 1)
factorial 5
val it : int = 120

## F# List

In F# is a semicolon-delimited immutable collection of values enclosed in brackets. Values have to be of the same type.

let numbers = [1; 2; 3; 4]
val numbers : int list = [1; 2; 3; 4]

To access the list elements use zero-based dot-notation

let secondNumber = numbers.[1]
val secondNumber : int = 2

Empty list is represented by empty brackets

[]
val it : 'a list = []

There are only two operations you can perform on a list. The first is **cons** (represented by the cons operator, **::**), which joins an element to the front or head of a list producing a new list. The second – **append** (represented by **@** operator) that joins two lists together producing a new list.

let smallerThanFive = 0 :: numbers
val smallerThanFive : int list = [0; 1; 2; 3; 4]

let largerThanFive = [6; 7; 8; 9]
let allNumbers = smallerThanFive @ [5] @ largerThanFive
val allNumbers : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]

## Pattern Matching

Pattern Matching is one of the powerful and complex features of Functional Language. You can think of it as a mighty switch statement which can match type of the input value type, extract the values, perform some operations, etc.

In the following code the **match** expression is trying to match **number** parameter with constant patterns **1**, **2** or variable pattern **n**.

let describeNumber number =
match number with
| 1 -> printfn "The number is 1"
| 2 -> printfn "The number is 2"
| n -> printfn "The number is %d" n
describeNumber 1
describeNumber 2
describeNumber 5

In the following code the **match** expression is trying to match **list** parameter with list patterns **[]**, **[_]**, **[_;_]** or wildcard pattern **_** to obtain the number of elements in the list.

let describeList list =
match list with
| [] -> printfn "Empty list"
| [_] -> printfn "The list with one element"
| [_;_] -> printfn "The list with two elements"
| _ -> printfn "The list with %d elements" (List.length list)
describeList []
describeList [1]
describeList [1; 2]
describeList [1; 2; 3; 4; 5; 6]

In the following code the **match** expression is trying to match **list** parameter with list pattern **[]** and a cons pattern **h :: t** splitting the list into the head element and tail list.

let splitList list =
match list with
| [] -> printfn "Empty list"
| head :: tail -> printfn "head: %A\ntail: %A" head tail
splitList []
splitList [1]
splitList [1; 2]
splitList [1; 2; 3; 4; 5; 6]

You could also use pattern matching in place of **if** statement. We can re-write factorial algorithm using pattern matching with **when guard**:

let rec factorial n =
match n with
| n when n < 0 -> failwith "The value n cannot be negative"
| n when n <= 1 -> 1
| n -> n * factorial (n - 1)
factorial 5
val it : int = 120

## function Keyword with Pattern Matching

You can use a simplified lambda syntax with pattern matching. Note, in this case you do not explicitly specify a function parameter because **function** lambdas accept only a single parameter that goes directly into pattern-match expression.

let rec factorial = function
| n when n < 0 -> failwith "The value n cannot be negative"
| n when n <= 1 -> 1
| n -> n * factorial (n - 1)
factorial 5
val it : int = 120

## List Module Functions

In F#, a **module** is a grouping of F# code. The List module contains functions that you can apply to the F# lists. Let’s take a look at a few of them.

List.length – given a list returns its length

List.length;;
List.length [1; 2; 3];;

List.iter – given a function and a list, iterates over the list and applies the function to each element

List.iter;;
List.iter (fun n -> printfn "Value: %d" n) [1; 2; 3];;
List.iter (printfn "Value: %d") [1; 2; 3];;

List.filter – given a function and a list, iterates over the list applying the function to each element and eliminating them from the resulting list if the function returns false.

List.filter;;
List.filter (fun n -> 3 > n) [1; 2; 3; 4; 5];;
List.filter ((>) 3) [1; 2; 3; 4; 5]

## Putting Everything Together

At this point you should have everything to understand and appreciate the code at the beginning of the post. For the sake of convenience I’m going to repeat it here once again.

let rec quicksort = function
| [] -> []
| x :: xs ->
let smaller = List.filter ((>) x) xs
let larger = List.filter ((<=) x) xs
quicksort smaller @ [x] @ quicksort larger
let sorted = quicksort [4;5;4;7;9;1;6;1;0;-99;10000;3;2]

Buy looking at this declarative-style code, it is easy to see that the quicksort is a recursive function that you apply to the list. The function is using pattern matching to split the list into the head and tail, then create two unsorted lists with smaller and larger numbers than the head, apply the function itself to those lists and as a final step – stitch those sorted by now lists with the head producing a final sorted list. Phew…

## Imperative Implementation of Quicksort Algorithm in C#

C# Quicksort from Pluralsight course F# Fundamentals by Liam McLennan (fast forward to 3:02):

public static void Quicksort(int[] elements, int left, int right) {
int i = left, j = right; int pivot = elements[(left + right) / 2];
while (i <= j) {
while (elements[i] < pivot) { i++; }
while (elements[j] > pivot) { j--; }
if (i <= j) {
int tmp = elements[i];
elements[i] = elements[j];
elements[j] = tmp;
i++; j--;
}
}
if (left < j) { Quicksort(elements, left, j); }
if (i < right) { Quicksort(elements, i, right); }
}

## References

1. F# Fundamentals by Liam McLennan

2. Programming F# 3.0, 2nd Edition by Chris Smith