Introduction to F#, 2nd part

Start by reading the 1st part here:

What if we need to add all elements in an array? Then I certainly need a for loop. NO, not in F# thanks to the cons operator \texttt{::}

F# uses lists for this. A simple list can be defined as follows:

let list = [1;3;2;4]

The cons operator in F# can both be used to filter out an element from a list and to add an element to a list. So the following is possible:

let list = [1;3;2;4]

let m = 5::list

and the result of m is [5;1;3;2;4].

And you can remove an element from the beginning of the list by doing

let m = [5;1;3;2;4]

let x::xs = m

Now x is 5 and xs is [1;3,2;4]

Usually you don’t remove an element in a \texttt{let}-statement because F# will complain that you didn’t cover all cases. But if you do it in pattern matching it makes great sense.

So lets say we would like to make a function that adds all elements in a list. It is done like this:

let rec sum =
  | [] -> 0
  | x::xs -> x + sum xs

In line 1 we declare a recursive function called sum. In line 2 we declare the pattern matching function. Line 3 asks: Is the input list empty then return 0. The 4th line: Is there an element in the list then take the first element and put into x and the remaining list in xs. And then add x to the sum of the remaining list recursively.

Now we can call the function like this

let m = [5;1;3;2;4]
sum m

and we get the correct result 15.

You see that everytime we call recursively we need some case that ends the recursion. If we continue to call recursively it will go into an infinite loop or get an error when the computer is out of memory. Our endpoint in part 1 was when n had reached one. Our endpoint in the sum-function is the empty list.

Now you know the basics of F# and what functional programming is all about.

Thank you for reading this short introduction to F#. I’m not going to teach you all aspects of F# but I will in the next blog post show you how to make a Sudoku solver that can solve the worlds most difficult Sudoku puzzle.

(As a side note F# also have imperative features such as for and while loops and you can even use it for object oriented programming, but this is beyond functional programming)

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