Introduction to F#, 1st part

I have in my life programmed in a lot of languages like Java, C, Assembler, Python, Object C, PHP, but I was first introduced to F# (F Sharp) when I began studying Computer Science at the Copenhagen University.

F# is a functional language. What does that exactly mean? It means that everything is functions. You might say that there are functions in Javascript, PHP, Python and so on, but a functional language is much more restrictive of what is called af function. This can sound tedious but there is beauty in it and if you know how to program in a functional style I believe that the quality of your code in non-functional languages will also improve.

So the functional style is much closer to a mathematical function. Lets look at a simple mathematical function:
  f(x) = x + 5

There are no posibilities to change anything once you have assigned a value to x. For instance you can set x=2 and get the folowing calculation: f(2) = 2 + 5 = 7

You plug in a number for x and get an answer back. This is a function. No more, no less. Lets see that in F#:

let f x =
  x + 5

In programming we need some way to make different choices. In other language we use an ‘if’ statement, but not in a functional language. First we see how it works in math:
  \newline  f(x)=  \begin{cases}  0 & \text{when } x = 0\\  x+2, & \text{otherwise}  \end{cases}

If we let x=5 we get f(5) = 5 + 2 = 7. If we let x= 0 we get f(0) = 0. This is a conditional function. If x is zero just return 0, but otherwise add 2. This is in F# done with pattern matching. Please note that the cases are evaluated in order so the first match will execute its statement after ‘->’ and skip the rest. So if x=0 the line 3 is executed and nothing else, and otherwise x is matched by the 3rd line and x+2 is executed. But lets take a look:

let f =
  | 0 -> 0
  | x -> x+2

The left side of ‘->’ is the pattern we are looking for. The right size is what we return.

Functional languages do not use for or while loops. “How is it even possible to do anything that other languages can do?”, you might ask. We look at math again! Lets assume that we want to make a function that takes an input n and we want to get the result f(n) = 1 + 2 + \ldots + (n-1) + n.

First of all we see that f(1) = 1. We also observe that f(n-1) = 1 + 2 + \ldots + (n-1). But then f(n) = f(n-1) + n
We put this in a conditional mathematical function:

  f(n)=  \begin{cases}  1 & \text{when } n = 1\\  f(n-1) + n, & \text{when } n > 1  \end{cases}

We now have a mathematical function that uses itself. You can say the function bites its own tail. Lets see what happens if we set n=3 and calculate f(3).

First we get
f(3) = f(3-1) + 3.

And then we calcuate f(3-1) = f(2) = f(2-1) + 2.

And last we get f(2-1) = f(1) = 1. We then go backwards

f(3-1) = 1 + 2 and

f(3) = (1 + 2) + 3 = 6

This is done in F# as follows

let rec f =   
  | 1 -> 1
  | n -> (f (n-1)) + n

When a function is calling itself it is called a recursive call. Recursion is used instead of for and while loop in a functional language. If we would have made this in Java or other non-functional languages we could have used a for loop, but we needed to keep track of the loop with an iterator i and a variable that would accumulate the sum. Hence the functional approach is much shorter and elegant.

Now continue to part 2 of this small introduction: Part 2

Leave a Reply

Your email address will not be published. Required fields are marked *