The Elegant Code I Wish I Can Write In C# 7

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):

// F# Quicksort    
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

// Creating a value via let binding
let x = 1

// F# Interactive output
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

// Creating a function via let binding

// function declaration
let square x = x * x

// function signature in F# Interactive output
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

// Creating a function via let binding

// function declaration
let add x y = x + y

// function signature in F# Interactive output
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

// Function application
let squareResult = square 2

// F# Interactive output
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

// Function application
let addResult = add 3 5

// F# Interactive output
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:

// Partial function application
let addThreeTo = add 3

// addThreeTo signature in F# Interactive output
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!

// Applying partially applied function to its arguments
addThreeTo 1

// F# Interactive output
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:

// Lambda expression
(fun x -> x * x) 2

// F# Interactive output
val it : int = 4

and

// Lambda expression
(fun x y -> x + y) 3 5

// F# Interactive output
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

// Higher-order functions

let applyAlgorithm f x y = f x y

applyAlgorithm (fun x y -> x + y) 3 5

// F# Interactive output
val it : int = 8

applyAlgorithm (fun x y -> x * y) 3 5

// F# Interactive output
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
// F# Interactive output
val it : int = 15

multiplyByThree 6
// F# Interactive output
val it : int = 18

multiplyByThree 7
// F# Interactive output
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 argumentitself.

// F# syntactic sugar

let formatOutput f x = f x

formatOutput (fun x -> sprintf "The value is %d" x) 5

formatOutput (sprintf "The value is %d") 5

// F# Interactive output
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

// Postfix notation
add 1 2

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

// Postfix notation
(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

// Symbolic operator

let (@%@) x y = x + y

// F# Interactive output
val ( @%@ ) : x:int -> y:int -> int

// yep, it's nothing more than just a function

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.

// Symbolic operator - infix notation
3 @%@ 4

// F# Interactive output
val it : int = 7

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

// Symbolic operator - postfix notation
(@%@) 3 4

// F# Interactive output
val it : int = 7

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

// Partially applied symbolic operator
let partiallyAppliedSymbolicOperator = (@%@) 3

// F# Interactive output
val partiallyAppliedSymbolicOperator : (int -> int)

partiallyAppliedSymbolicOperator 4

// F# Interactive output
val it : int = 7

 

Recursive functions

To define a function that can call itself use rec keyword

// Recursive function
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

// F# Interactive output
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.

// F# list
let numbers = [1; 2; 3; 4]

// F# Interactive output
val numbers : int list = [1; 2; 3; 4]

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

// F# list
let secondNumber = numbers.[1]

// F# Interactive output
val secondNumber : int = 2

Empty list is represented by empty brackets

// F# list
[]

// F# Interactive output
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.

// F# list cons operation
let smallerThanFive = 0 :: numbers

// F# Interactive output
val smallerThanFive : int list = [0; 1; 2; 3; 4]

// F# list append operation
let largerThanFive = [6; 7; 8; 9]

let allNumbers = smallerThanFive @ [5] @ largerThanFive

// F# Interactive output
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.

// Pattern matching
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
// The number is 1

describeNumber 2
// The number is 2

describeNumber 5
// The number is 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.

// Pattern matching
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 []
// Empty list

describeList [1]
// The list with one element

describeList [1; 2]
// The list with two elements

describeList [1; 2; 3; 4; 5; 6]
// The list with 6 elements

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.

// Pattern matching
let splitList list =
    match list with
    | [] -> printfn "Empty list"
    | head :: tail -> printfn "head: %A\ntail: %A" head tail


splitList []
// Empty list

splitList [1]
// head: 1
// tail: []

splitList [1; 2]
// head: 1
// tail: [2]

splitList [1; 2; 3; 4; 5; 6]
// head: 1
// tail: [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:

// Pattern matching in recursive function
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

// F# Interactive output
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.

// Pattern matching in recursive function
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

// F# Interactive output
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;;
// ('a list -> int)

List.length [1; 2; 3];;
// val it : int = 3    

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

List.iter;;
// (('a -> unit) -> 'a list -> unit)

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

// or you could re-write it as
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;;
// (('a -> bool) -> 'a list -> 'a list)

List.filter (fun n -> 3 > n) [1; 2; 3; 4; 5];;
// val it : int list = [1; 2]

// or you could re-write it
// using symbolic operator postfix notation

List.filter ((>) 3) [1; 2; 3; 4; 5]
// val it : int list = [1; 2]    

 

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.

// F# Quicksort
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]

// F# Interactive output
// val sorted : int list = [-99; 0; 1; 1; 2; 3; 4; 4; 5; 6; 7; 9; 10000]

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):

// C# Quicksort
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