I had written a post on Functions in F# a couple of days ago and Binil posted a comment which prompted me to post a follow up to add some information that I left out in the original post.

F# Syntax

F# has two syntax forms available – a lightweight syntax and a verbose syntax. The lightweight syntax uses indentation to mark the beginning and end of code blocks. This naturally results in more concise code. The verbose syntax uses additional keywords to demarcate code blocks making the code lengthier than it needs to be but it makes the code less sensitive to indentation (imagine copy-pasting and sending code in email etc).

The lightweight syntax is on by default. You can explicitly set it to on by using

#light

The verbose syntax is always on which means you can still use the verbose keywords even if the lightweight syntax is on.  We can enforce the verbose syntax by switching off the lightweight syntax as follows

#light “off”

The lightweight syntax is in more prominent use than the verbose syntax and it seems that going forward the verbose syntax might be obsolete.

Only spaces can be used for indentation in F#, TABs are not accepted. Visual Studio by default converts TABs to spaces. This can be set in Tools –> Options dialog under Text Editor –> F# –> Tabs.

Tail Recursion

I had mentioned about recursive functions in my previous post on Functions in F# but I did not mention anything about tail recursion. Given the importance of recursion in F#, this is a very important topic and I want to thank Binil for bringing it to my notice.

First, let me provide some background info on what is bad about recursive functions and why tail recursion is the preferred way to write recursive functions.

When is function needs to be executed, a block of memory is allocated on the system stack for the function and is called a stack frame. When the function completes execution, this memory is reclaimed and is called unwinding the stack.

Recursive functions call themselves repeatedly until an exit condition is met. This means that a new stack frame has to be created each time the recursive call is made. Given enough nested function calls there wouldn’t be any more space on the system stack and would cause an undesirable condition called stack overflow. The program execution is terminated forcefully by the runtime.

If the function calls are not recursive, for example calling a function 1000 times in a for loop, the memory block for a function can be reclaimed when the function execution is over. So what we need to try to achieve is to write the function in such a way that the stack frame of the calling function need not be maintained while execution proceeds to the next function call. The way to do this is to make the recursive call as the last statement in the function. When we do that the compiler produces different code which allows the stack frame of the calling function to be unwound and the memory reclaimed, in effect making it similar to calling the function in a loop. This technique is called tail recursion.

Let us look at some code to make this more clear. Here is the recursive implementation of factorial that I wrote in my previous blog post.

let rec factorial x=
    if x <= 1 then
        1
    else
        x * factorial (x-1)

Here it might look as if the recursive call is the last statement in the function, but it is not. It would become clear if we wrote it this way:

let rec factorial x=
    if x <= 1 then
        1
    else
        let product = x * factorial (x-1)
        product

Now it becomes clear that the last statement in the function is returning the value of product. We also see that the function has to maintain the value of x in its stack frame and multiply it with the value returned by the recursive call. So if the function is written as shown above, there is no way to reclaim the stack memory until the chain of recursive calls return. So let us re-write the function in using tail recursion.

let factorial x =
    let rec tailRecFactorial x prod =
        if x <= 1 then
            prod
        else
            tailRecFactorial (x-1) (prod * x)
    tailRecFactorial x 1

Here we have a nested function which takes the product up to the current stage as a parameter which means nothing needs to be stored on the stack of the calling function. The stack frame can be safely reclaimed. The compiler is able to spot the tail recursive calls and generates code as if the function was called in a loop. Execution returns the original calling point when the exit condition is met.

The method I showed above to achieve tail recursion is called accumulator pattern. Another way is to use Continuations.

Trivia

When I was writing the non tail recursive factorial function, by mistake I wrote it this way:

let rec factorial x =
    if x <= 1 then
        1
    else
    x * (factorial x-1)

Can you spot the problem ?

Hint: It causes a StackOverflowException when executed.

Wikipedia says that

…functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions…

The point I wish to make here is that functions are the  most important “things” in a functional programming language. You can say that functions are “first class citizens” in a functional programming language. This means that functions can be passed around as parameters and return values of other functions, just like any other data. Functions which can take other functions as parameters and/or return values are called Higher-Order Functions.

Functions and Type Inference

Here is an example of a simple function in F#.

let triple x = 3 * x

Here triple is the name of the function and x is the name of the parameter passed to the function. Contrary to C# naming convention for function, F# uses camel casing. Even though we have not specified any type information, the compiler is able to infer that this function takes an integer as parameter and returns an integer. This is called Type Inference and makes your F# program more concise.

How did I know that the compiler inferred the parameter and return value as int? I typed in the above functional declaration in F# interactive and terminated it with ;; and hit Enter. F# showed me:

val triple : int –> int

This means that triple is a function which takes an integer as parameter and returns an integer. If we try to call the function with a float as parameter

triple 3.0

it will spit out an error message as follows.

stdin(4,8): error FS0001: This expression was expected to have type
    int   
but here has type
    float   

We know that * (multiplication operator) works with floats as well, so why this error ? The reason for this is that in the absence of any additional type information the compiler simply defaulted the type to integer. So triple is a function which can take an integer as parameter and return an integer which is equal to three times its input. It is equivalent to the following C# function.

static int Triple(int x)
{
      return 3 * x;
}

Since the function expects integer, a parameter of type float will produce an error.

So what do we do when we need a datatype other than the default type that the compiler is able to infer? We give a hint to the compiler via type annotation.

let triple (x: float) = 3.0f * x

Note: In the above example type annotation is not strictly required because the compiler would infer x as float because 3.0f is float. But it does show you how to annotate a function parameter with its type.

Higher Order Functions

The functions mentioned above are not a higher-order functions because they do not take a function as parameter, neither do they return one. List.map and List.filter are examples of higher order functions. List.map takes a function and applies it to each item in the list (also passed as parameter to it) and returns a new list with the output values. List.filter takes a function and list as parameters and returns a new list. The output list contains those values from the input list for which the input function returned true. An example is shown below which makes use of both these higher order functions.

let triple x =
    3 * x

let isEven x =
    x % 2 = 0

let actOnEven action numbers=
    List.map action (List.filter isEven numbers)

[<EntryPoint>]
let main(args:string[]) =
    let results = (actOnEven triple [1 .. 10])
    Console.WriteLine (results)
    0

Here actOnEven is itself a higher order function.

Recursive Functions

Recursive functions are functions that call themselves. An important tenet of functional programming is the use of recursion instead of looping. We can create recursive functions using the following syntax.

let rec factorial num =
    if( num <= 1) then
        1
    else
        num * factorial (num - 1)

The rec keyword is a helping hand to the compiler for type inference. Personally, I don’t like it but I think they couldn’t find a way around it.

Function Currying

Currying (named after Haskell Brooks Curry) is an interesting technique in which you pass one of the arguments to a function and it returns another function which takes the rest of the arguments. For eg., consider the function

let add x y = x + y

If you run this in F# interactive, you will see the following message:

val add : int -> int –> int

This means that add is a function which takes an integer and returns a function which takes another integer as parameter and returns an integer. So if we call add with just one parameter, it will return another function which takes the second parameter.

let addToTwo = (add 2)

To be clear, addToTwo is a function that takes one integer parameter and returns an integer.

For eg,

addToTwo 8

will return 10.

Here addToTwo is the curried function and this technique is called function currying. Although this may look like a strange and useless language feature, it has interesting and powerful applications in functional programming (like the pipe forward operator). I will write more about this in future blog posts.

Nested Functions

In F#, a function can contain another function. Here is a simple example.

let printList numbers=
    let print num=
        printfn "%i" num
    List.map print numbers

Here print is a function nested in printList.

Some of the feature that I have mentioned here would be new to C# programmers and might feel a little strange. But have hope, for all will become more clear with time. We need to see some solid examples to appreciate the power of some of them. I have mostly presented useless examples but I hope a reader would have gleaned atleast a little information about functions and its usage in F# from this post. There is more to write but it is getting late (3 am) and tomorrow is a working day, so I gotta go. Will be back with more on F#.

References:

Programming F#

Expert F#

let display message =
    printfn "%s" (message.ToString())

let powerOf x y = x ** y

let powerOf2RaisedBy = powerOf 2.0

[<EntryPoint>]
let main(args) =
    display (powerOf2RaisedBy 3.0)
    0