Functional control structures

The most immediate question that any procedural programmer will want to ask is how to implement all of the standard control structures – the if statement and iteration in all its forms.

The if statement is relatively easy as all you need to do is consider the usual if..then..else type construct as a function that returns either the “then” function or the “else” function – this is good functional programming.

Notice that writing functions one after another implies the default order of execution so we haven’t completely avoided the procedural.

The enumeration loop is more problematic because most loops involve the idea of changing the value of something within the loop and this isn’t allowed if what is in the loop is immutable.

There are various ways that a functional language can avoid iteration. For example, to display the first ten integers you can use:

let nums=[1..10]
printfn "%A" nums

The [1..10] is just a specification for a list in F# and you can avoid many explicit iterations by simply converting them into a list and a list operation. This is often called a "List comprehension" and you can find similar constructs in languages such as Python and Ruby that are not generally regarded as functional languages.

For example, suppose you want to print the squares of the first ten integers you can use:

let nums=[1..10]
let sqr x = x*x
let ans=List.map sqr nums
printfn "%A" ans

 First we create a list of the first ten integers, then define a function to perform the square operation and finally apply the sqr function to each of the values in the list. The List.map function takes any function and applies it to each member of the list and returns a new list of results.

If you want to use a variable iteration range you can, as in:

let nums=[1..n]

as long as n has a value when this is evaluated then it all works.

Notice that the map function takes a function as one of its parameters.

In functional programming functions can be used in the same way you use any other data type. When used in this way they are called “first class” functions.

There are lots of list processing functions and mastering these is a large part of mastering functional programming in F#.

Anonymous functions

This is a good place to introduce the notion of an anonymous function. Often functions are just used once and there is no need to give them a name – you just want to use them.

F# supports anonymous functions, often called lambda expressions, that look just like C# lambda expressions. For example the calculation of the squares could have been written:

 let ans=List.map (fun x -> x*x) nums

The fun keyword declares a function and the “arrow” can be thought of as showing how the parameters are transformed into the result.

You can take this “anonymous” approach to functions and nest function calls to reduce the entire generation and printing of the squares to a single statement:

printfn "%A" (List.map 
        (fun x -> x*x) [1..10])

It is possible to take this approach so far that it becomes very difficult to follow what an F# program is doing – so beware.

Folding

What about finding the sum of all of the values in a list? The simple answer is that there is the sum function which returns the sum of a list. For example:

 printfn "%A" (List.sum nums)

However this is a bit of a cheat as it doesn’t really give you any idea of how to convert an iteration with a “running computation” of a more general kind into functional form.

You could say it hasn’t illustrated how mutable becomes immutable.

One solution to this more general problem is the use of a “fold” function. The best way to explain folding is via an example.

The List.fold_left function accepts a function, an initialiser and a list as its parameters. The function plays the role of an “accumulator” in the sense that it collects up the results of the function applied to each element of the list. To sum a list for example you might use something like:

printfn "%A"
(List.fold_left (
   fun a x-> a + x) 0 [1..10])

The accumulator function in this case is:

fun a x-> a + x

the x parameter is set to each value of the list in turn and the a parameter is the result of the function applied to the previous list element. The 0 is the initialiser and sets the a parameter to zero in the function’s first call.

If you are following this explanation and are a long-time procedural programmer then you should be spluttering – but this is a loop in disguise!

Well yes, but… think of it this way instead.

The function is applied to the first element of the list x0:

f(0,x0)

where the value of a is provided by the intialiser. Next it is applied to the second element in the list x1 but this time a is set to the result of the function applied to the first element, that is:

f(f(0,x0),x1)

The third evaluation is similar:

f(f(f(0,x0),x1),x2)

and so on. Now you can see that what you have here is a nested function evaluation:

f(f(f(f(…(0,x0),x1),x2),x3)…,xN)

Hence folding is building nested function evaluations without having to write it all out manually.

Now is folding a loop in disguise or something different?

For the record the fold_left function nests taking the list elements left to right and fold_right takes them in the reverse order.

You should also appreciate that folding is a very general and powerful technique that really does allow you to do more or less anything you could do by iteration.

For example, you could use the Cons function, which is implemented as an operator :: (double colon) to build up a new list.

That is, 1::[2;3;4] adds the number one to the start of the list to produce [1; 2; 3; 4]. To make use of this in a fold to reverse the order of the values you could use something like:

printfn "%A"
  (List.fold_left
      (fun a x-> x :: a) [] [1..n])

In this case the “accumulator” function:

fun a x-> x :: a

takes each element of the list and adds it to the accumulator list being built up in a. A moment’s thought should convince you that this results in the list being reversed. Notice the use of the null list [ ] to initialise the fold.

<ASIN:0470242116>

<ASIN:0521663504>