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)

Leave a Reply

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