F# Survival Guide

Up to this point in the book, we’ve learned about primitive data types, basic conditional structures, imperative looping constructs and simple collection types in the form of tuples and arrays. Arguably, most of what we’ve learned lives comfortably in the realm of imperative and OO programming. These are mostly familiar concepts encountered in other languages, and you should quickly be at ease using them on a regular basis in F#. This puts us in a good position to peel the onion and start exploring F#’s functional side.

By studying functions and related functional programming concepts, we will be able to take advantage of F#’s more powerful and elegant data structures and mechanisms including lists, sequences, generic types, asynchronous processing, etc.

To get started, we’ll discuss what functions are, how they are defined and used, and how they interrelate to form powerful structures that are functional programming’s raison d'être.

Functions

As we saw in Chapter 1, mathematical functions are, in essence, transformations. They accept inputs and emit outputs. They produce no side effects, i.e., the inputs are unaffected by the function and the function does not affect global state. Functions are also predictable in that the same inputs will consistently and reliably produce the same outputs. Let’s take the square root function, for example. The square root function takes as input a single parameter and returns a single return value. The input value and the output values are related solely by the given function, and the input value is unaffected by the execution of the function. The function will always return the same output for a given input. Before we delve into functional concepts, it makes sense to see how we define and work with functions in F#.

Defining Functions in F#

To define functions in F#, we use the let keyword, followed by the function name, an optional parameter list, the assignment operator =, and the body of the function. The general form of an F# function is as follows:

Every construct in F# is an expression; therefore, it evaluates to a value of a given type. The following examples demonstrate how to define functions in F#:

One interesting definition above is that of the function foo. “Wait a minute - isn’t this just a value, like all the other values we’ve seen do far?” Yes, it is. What this tells us is that a value is just another type of function – a function that takes no parameters and evaluates to a known quantity. This quantity may be a constant, or something computed. What this helps to show, I hope, is that as far as F# is concerned, there is no real difference between a value and a function. They are synonymous, and can be used very naturally together. We will explore this concept throughout the text.

Function Parameters

Let’s now take a look at the next function, f. This function is more traditional in that is accept a parameter. We will visit the other two functions, g and sumVals, in turn.

Here we have a function named f. This function take a single parameter, x. Note that we do not specify the parameter’s type explicitly. This forces the F# type system to try to figure out x’s type based on context. Since F# sees that the function body sums x with the integer 1, it assumes that x must be an integer (since 1 is an integer). If we were to replace the 1 with 1.0, F# would assume x is a float.

Notice that we have not defined a return type for the function. I’d like to make two points about this. First, instead of thinking about a function “returning” a value, it helps to think about a function “resolving to a value” or “evaluating to a value.” (Although we still sometimes talk about a function returning a value, we really mean it resolved to a value). Second, F#’s type inference can generally deduce the type to which the function resolves.

Of course, functions can have multi-line bodies. In the following example, we write a function that determines the minimum value of two inputs. This function is for demonstration purposes only. In a real-world implementation, we would implement this more elegantly or, more likely, use the System.Math.Min() function.

Note that we use whitespace to vertically align the function body. Remember that in F#’s #light mode (the only one we’re using in this book), whitespace is significant, and is used to define semantically related code blocks.

In some cases, F# may not be able to figure out the exact type of a function’s arguments. The cause for this varies, but includes situations where the argument is part of an operation in the function body where one of several types is equally good. In the following example, we define a function countVowels that counts the numbers of vowels found in a given string. This is a contrived example, but is useful for making the point that sometimes we need to help out the F# type inference system:

// Attempt #1: ERROR. F# cannot determine str's type.
let countVowels str =
    let mutable vowels = 0
    let lcs = str.ToLower()
    for i = 0 to lcs.Length - 1 do
        if str.[i] = 'a' || str.[i] = 'e' ||
           str.[i] = 'i' || str.[i] = 'o' ||
           str.[i] = 'u' then
               vowels <- vowels + 1
    vowels

In the example above, F# cannot reliably determine the type of the parameter str, so it cannot compile the function. To assist F#, we need to explicitly define str’s type. Here is the new, fixed function:

// Attempt #2: OK. With addition of type info, F# can determine str's type.
let countVowels (str : string) =
    let mutable vowels = 0
    let lcs = str.ToLower()
    for i = 0 to lcs.Length - 1 do
        if str.[i] = 'a' || str.[i] = 'e' ||
           str.[i] = 'i' || str.[i] = 'o' ||
           str.[i] = 'u' then
               vowels <- vowels + 1
    vowels

Notice the function signature. It now contains some added type information for the F# compiler to use. Here, we are explicitly stating that str is of type string. Once we do this, the function compiles fine. Observant readers may also have noticed the addition of parentheses around the parameter and it’s type signature. When specifiying explicit types for function arguments, you must use the parentheses for F# to recognize the type properly, otherwise, based on precedence rules, it evaluates the intent incorrectly.

We can use this same syntax for functions that accept multiple parameters as well. Below are a few examples:

byref Parameters

Sometimes you need to change function parameters, e.g., when interoperating with other .NET languages. To accomplish this in F#, you need to use a combination of mutable values, the address-of operator (&), and the byref keyword, as demonstated in the following example:

In this example, we see that incrementParam’s argument i in is of type int byref. The byref keyword tells the compiler to expect the address of a mutable value. In the next line, we use the mutable keyword so that when we pass j to incrementParam, the function can successfully change j’s value. Lastly, when we call incrementParam, we supply the address of the mutable value, and we do so by using the address-of operator (&).

Note that byref parameters work with value types such as primitives. We will look at more advanced data structures and how to pass and change them in subsequent chapters.

Function Types and the Weird Arrow Notation

The power of an F# function stems in large part from the fact that it can take one or more functions as parameters and return a function as a result. Before we can explore the nature and consequence of this idea, let’s take a closer look at function types, which will give us the background we’ll need to delve more deeply.

Like other expressions in F#, functions evaluate to a value, which means they have a concrete type. Let’s take our simple example from above:

When we define this function using theF# Interactive Console, we receive the following feedback:

This tells us that f is a function (indicated by the -> symbol, which I’ll call the function symbol). This function takes a single integer paramter (parameter types are listed to the left of the -> symbol) and evaluates to an integer (the evaluation type is listed to the right of the -> symbol). This notation seemed very strange to me at first, until I realized why F# reports function types like this – and it’s back to the mathematical definition of a function.

Remember that a mathematical function is really a tranformation. It transforms inputs to outputs in a reliable and regular manner. The function symbol (->) is therefore a very natural way to remind us what’s happening – the input is being transformed (or mapped) to an output of a given type. The rightmost value (the one to the right of the function symbol) is the final type of the function. In other words, it is the type to which the function evaluates.

Take note that this notation is not a convenience, nor is it trying to be “especially F#-ish” or cerebral. It is a fundamental and important notation that reflects the nature and of the language. Becoming familiar with arrow notation will help you greatly in both learning and using F#. I made the mistake, at first, of thinking of it as “just another way to display what a function accepts and returns.” This mind set made grasping some of the functional programming concepts more difficult than they should have been. I encourage you not to follow in my footsteps here. OK, let me hop off my soapbox and discuss another example:

Here, we’ve surrounded the parameter x with parens[1]. The only difference between f and g is that we used (optional) parentheses to clearly indicate that x is a parameter. Like f, g is a function that accepts a single integer as input and returns a single integer as output. Semantically, f and g are identical.[2]

let sumVals x y = x + y // apply operator + to values x and y
val sumVals : int -> int -> int

Here we see that sumVals returns an integer (the right-most type following the last -> symbol). We can also see that it accepts 2 integer values as input (the first two ints listed from left to right).

Given the above explanation of functions as transformations, you would probably assume that F# would display sumVals’s type something akin to this: int, int -> int[3]. The reason F# displays sumVals’s type as int -> int -> int is rooted in lambda calculus.

In lambda calculus, all values, even constants, are represented as functions. Due to these underpinnings, F# functions only ever take a single parameter and return a single value. Although this doesn’t appear to be the case due to syntactic sugaring in the language, F# enforces this idea conceptually[4]. If we now take the “lambda calculus view” of the sumVals function, we can think about its type as being the following:

The arrow symbol is right-associative, which means that you read it from right-to-left to discern it’s meaning. Here, we start from the right and look at the two operands on either side of the -> symbol. The fact that the arrow is right associative means that we can put parens around the rightmost expression and preserve the original meaning, as we’ve done in this example.

Here’s where things get functional (and maybe confusing – but bear with me and we’ll work through it). This type tells us that sumVals is a function that takes an integer parameter (int ->) value and evaluates to (returns) a new function. This new function accepts a single integer parameter and, in turn, returns an integer. This is what (int -> int) means.

To make things more confusing, invoking a function is left-associative. This means that we read function invocations from left-to-right in order to group or associate elements. So, when we see a function definition like sumVals x y, semantically, it’s the same as writing (sumVals x) y. Although this is not legal F# syntax for defining a function, it is legal syntax for invoking one. Breathe deeply. Repeat as necessary. Let’s unravel this and see what it all means.

F# reports it’s type as int -> int -> int. We will write it here as int -> (int -> int) to remind us what’s really happening. Now when we invoke sumVals like this:

Partial Function Application

What makes this all possible is that F# supports what’s called partial application of functions. To “partially apply” a function, you only supply a subset of the arguments that the function expects. In other words, you don’t pass in all the arguments at once. When you omit arguments, F# generates a new function that holds onto/remembers the arguments you passed in and “waits” for the other parameters to be supplied.[5] Let’s run the following code in the F# Interactive Conole.

// Another way to say this is that “sumX is a partial application of sumVals.”

let sum = sumX 20
// Invokes sumX, passing in expected int (parameter y from original)

When we run the code above in the F# Interactive Console, F# reports back the following:

When we call sumVals 10, F# sees that not all of the expected arguments were provided. In response, it generates a new function. This new function remembers the value of the parameter that was passed in (10), and generates code to add 10 to whatever is passed in next. In the example above, we capture this newly generated function and store it in sumX. We can now call, a.k.a., evaluate, sumX with an integer value, i.e., its expected argument. The code in sumX knows to add this value (20) to the original “held” value 10 – and, viola, we compute the sum (10 + 20 = 30). Let’s look at a few more examples:

This function appears to take zero parameters. In actuality, it takes a parameter of type unit. It also returns a value of type unit. Here is what the F# Interactive Console says when we run this function:

Here we see that this function, although it appears to accept two parameters, is really a function that accepts a single parameter of type int and returns a function that takes a single parameter of type string. This new function subsequently evaluates to the type unit. Based on this explanation, we could rewrite this function’s type as int -> (string -> unit).

Given the fact that F# functions only ever take a single parameter and return a single value, this “chaining” effect takes place regardless of the number of parameters. For example:

Not surprisingly, the type of this function as reported in the F# Interactive Console is:

Understanding that the function symbol -> is right-associative, we could re-write this type as follows:

This tells us that function f accepts a parameter of type int and causes the generation of a function that itself takes an int, which, in turn, generates a function that takes an int, etc. The final function evaluates to a value of type unit.

The good news about all this? In most cases, you can simply read a function’s signature from left-to-right and understand what types of arguments the function expects, and what type it returns (the right-most type displayed in the function’s signature).

So, what if you have a function that needs to accept multiple arguments, e.g., when you define a point and you need both the x and y coordintes? Enter our old friend the tuple. In order to pass in “multiple” values to a function, you can use simple (or more complex, as we’ll see) collections like tuples. Since a tuple is a single entity, you are not violating the rule that F# functions only ever take a single parameter and return a single value. The following example ensures that the caller supplies both an x and a y coordinate for a point:

As we learned earler, tuples are defined by surrounding comma-separated values with parens. translatePoint, therefore, does not accept 2 parameters, but accepts a single parameter of type tuple. Case in point, F# reports the type of this function to be:

This tells us that translatePoint is a function (->) that takes as input a tuple of type int * int and evaluates to unit.

Functions defined as taking a single tuple cannot be partially applied. In general, functions that accept one or more individual parameters (OK, we know that they only really accept one parameter but F# lets us think of them at taking multiple ones) separated by spaces is preferred, as they can participate in more advanced scenarios such as composition. We will cover more advanced uses of functions later in the chapter.

Now that we know how to define basic functions, and know how to read F#’s function type notation, we are in an excellet position to explore additional functional concepts.

Nested Functions

F# supports defining functions within functions. We refer to these as nested functions or inner functions. Nested functions are typically used to encapsulate “helper” functionality inside the enclosing function. Because functional programs tend to execute loops via recursion, we sometimes need parts of functions to perform recursively – to perform local looping. Using nested functions makes implementing “partial recursion” as straight-forward as possible. The following example was taken from the F# Wikibook:

Notice that in this example, we define a function called loop, which is both nested and recursive (a common situation). We can see that sumOfDivisors calls loop (see last line) to perform the bulk of the computation. Certainly, the function loop could have been made external (not inner) and called from sumOfDivisors; however, by making loop a nested function, we are indicating a “more intimate” relationship between the outer function and its helper, and properly isolate the functionality where it belongs.

In addition to demonstrting the relationship between functions, there is another benefit of using nested functions – the nested function can access and use the values (variables, in case you’ve been yearning for that word for a while) defined in the outer function. This obviates the need for sumOfDivisors to pass n as a parameter to loop, as it would need to do if loop were made a regualr, non-nested function.

Key Functional Concepts

Remember from your high school or college days that mathematical functions obey strict mathematical rules. For example, functions can be used in standalone fashion, e.g., f(x), or they can be composed, e.g., f(g(x)). They can be also be defined recursively, can produce infinite sets of outputs, etc. Many of these concepts are directly reflected in functional programming languages; therefore, to really grasp and harness the power of functional programming, you need to understand a handful of functional concepts. Otherwise, the different mechanisms that we cover will feel nothing more than academic, and could result in frustration and confusion.[6]

Recursion

The first functional concept that we need to become familiar with is that of recursion. In mathematics, and in programming, a recursive function is one in which the function being defined is applied within its own definition. To begin our discussion on recursion, let’s use the tried-and-true factorial example. In F#, we define can define a recursive factorial function as follows[7]:

Notice the new keyword rec. Whenever you define a recursive function in F#, you must use the rec keyword. Using the rec keyword does not change the function’s fundamental type. As defined, our factorial function has type int -> int. Let’s look at what happens when we call factorial:

factorial 5 =
     = 5 * factorial (5 - 1)
     = 5 * 4 * factorial (4 – 1)
     = 5 * 4 * 3 * factorial (3 - 1)
     = 5 * 4 * 3 * 2 * factorial (2 – 1)
     = 5 * 4 * 3 * 2 * 1
     = 120

Each time the function is called, the runtime allocates a new stack frame, inherently preventing side-effects, which is one of the goals of functional programming.

In order to prevent infinite loops, all recursive functions must have a base case, which triggers termination. In the factorial example, the base case is where n is less than or equal to 1. When execution state satisfies the base case, this triggers termination and the stack unwinds normally.

There are a few rules of which you should be aware regarding using a recursive functions. A recursive function must:

· call itself, recursively (unless the initial condition satisfies the base case)

I think the key to understanding recursion is to realize that a function calling itself is no different than, e.g., function A calling function B. The same exact processing occurs in both cases – the runtime creates a new stack frame, the current instruction pointer and return address are stored, etc. There is nothing “magic” about the stack frame in the standard recursive case. The stack is the stack, and behaves exactly the same way in both the non-recursive and recursive cases.

Due to the fact that recursive calls inherently prevent side effects, functional programming prefers recursion over imperative iteration structures.

When defining recursive functions, you can define two recursive functions that call one another. These functions are called mutually recursive functions. The following example of mutually recursive functions was taken from Expert F# by Don Syme:

As you can see, the function even relies on the function odd, and the function odd relies on the function even. We define mutually recursive functions via the keyword and, as shown.

One of the big issues inherent with recursion is the possibility of stack exhaustion, i.e., the system runs out of stack space. This can occur if the function requires too many iterations in order to reach the base case. The question that normally comes up here is, “If functional programming favors recursion, and recursion is subject to stack exhaustion, what’s the use? How can I build real programs?” Good question. Enter tail recursion.

Tail Recursion

In standard recursion, the runtime needs to build up the stack, frame by frame, so that it can eventually complete its set of pending operations. Let’s look at a conceptual diagram of calling our factorial function with the value 3:

As you can see, the stack is built up, frame by frame, from the bottom up. The runtime needs to retain each stack frame in order to store information that it can use to perform the pending multiplications, e.g., 3 * factorial(2) and 2 * factorial(1). This means that the ultimate size of the stack is dependent upon the number of calls. If the number of calls is large, the stack will grow too large for available memory and – kaboom – stack overflow. We can eliminate this issue by writing our recursive functions using a tail recursion.

A tail recursive function uses a special case of recursion in which the last instruction executed in the method is the recursive call - there is no “pending operation” for the runtime to worry about. F# and many other functional languages can optimize tail recursive functions. Since no extra work is performed after the recursive call, there is no need for the function to remember where it came from or to store information about pending operations. F# optimizes tail-recursive functions by telling the CLR to drop the current stack frame before executing the target function. As a result, tail-recursive functions can call itself indefinitely without consuming stack space.

To convert a standard (non-tail-recursive) function into a tail-recursive function, you need a way to eliminate the need for the pending operation. If you think about it for a second, what does recursion do? It “builds up” a result over one or more iterations. If we could somehow change the “building up” of the result and use another mechanism to eliminate the need for the runtime to allocate a stack frame per call, we could create a tail recursive function and avoid stack overflow. The standard solution is to use an auxiliary parameter.

The following text was taken from this site. I liked this explanation, and couldn’t think of a better way to say it:

A non-tail recursive function can often be converted to a tail-recursive function by means of an "auxiliary" parameter. This parameter is used to build up the result. The idea is to attempt to incorporate the pending operation into the auxiliary parameter in such a way that the recursive call no longer has a pending operation.

To turn our standard recursive factorial function into a tail-recursive function, we need to introduce a value that builds up (a.k.a., accumulates) the answer as the function executes. Here is a tail-recursive version of the famed factorial function:

Note that this version does not contain a pending multiplication. Instread of the runtime needing to keep stack frames around so that it can eventually calculate the final result, we’ve used an accumulator to build up the result as we go. The key here is that the last thing the function does is call itself, thus avoiding any pending operation. The “last thing the function does” does not have to be lexically the last line of the function, although it often is. I like Wikipedia’s description:

Note that the tail call doesn't have to appear lexically after all other statements in the source code; it is only important that its result be immediately returned, since the calling function will never get a chance to do anything after the call if the optimization is performed.

Some people don’t like the “uncleanliness” of calling a tail recursive function with an extra accumulator parameter, so they will often provide a helper function that hides the accumulator from the call site. Here is an example of a “clean” tail-recursive factorial function that uses such a helper function to hide the fact that the accumulator exists:

// Helper function that hides the accumulator. This is the one called by client code.
let fact n =

I hope that the previous discussion helps you to better understand recursion, and the ideas and implementation techniques behind tail recursion. We continue our exploration of functional programming concepts with high order functions.

High Order Functions

There is a lot of terminology that you need to master when you start living the functional lifestyle. One of the core concepts that you need to be familiar with is that of the high-order function. A high-order function is a function that either takes a function as a parameter or returns a function, a.k.a., evaluates to a function, as an output – or does both. We saw a little of this when we discussed partial application of functions (which we will revisit again shortly).

Since F# functions are just values, it’s very easy to pass functions around. (If it helps, think about this as passing a pointer to some executable code). Let’s look at a few examples. First, we’ll define a function foo that takes as an integer n argument and a function f (yes, we will pass in a function). The function f will itself accept an integer as input and return an integer as output. The players:

Now, let‘s define another high-order function addone that returns a function. We can then use addone as an input to our beloved foo:

High order functions are a staple of functional programming – but as shown, they can be a little cumbersome to use. In order to have functions to supply to foo, for example, we fist need to define them, e.g., square and cube in our example. These functions exist solely so that we can pass them into foo. Wouldn’t it be great if could by-pass defining these “side” functions and simply supply the functional code to foo directly? Well, it turns out that we can. This is the role of lambda functions.

Lambda Functions

I think the name lambda function sounds scary. It sounds complex. When I hear this term, I think of crazy-haired professors with thick glasses and white lab coats scribbling on dust- filled chalkboards.[8] I am happy (and relieved) to say, that lambda functions are nothing more than functions without names. Another term people use for them is anonymous functions. What possible use could a nameless function have?[9]

Lambda functions are used in functional programming where you want to define or execute code in-situ. They are a convenient way to write code where you’d normally need to write a call to a helper function – like square and cube in our previous example.

If you’re familiar with C# or Java, think “local event handler” or “anonymous delegate” or (in the latest version of C#) “lambda expressions.”

You define a lambda function using the keyword fun. The fun keyword introduces the function. Lambda functions can accept input parameters and, of course, evaluate to a value (return output). The following example defines a lambda function called cube that returns the cube of the given input parameter:

This function has no name. The symbol n following the keyword fun is a parameter – not the name of the function.

This example binds the identifer cube to the function code. Once bound, you can use the function like any other:

As you can see, there is fundamentally no difference between a lambda function and a normal F# function (look at cube’s type, for instance). Note that lambda functions are a convenience. You can always implement the same code without using lambdas. Again, I refer you our previous foo example. Now that we know what lambda functions are, let’s rewrite the example to use them:

As you can see, we simply replaced the calls to the helper functions with lambda functions. Executing these lines of code yields identical results to the previous example. We will use lambda functions extensively in functional programming. Many of the built-in types and modules, e.g., List and Seq, define functions that accept function arguments. Most of the time, we supply these arguments in the form of lambdas.

Mapping

Now that we understand functions and their basic mechanics, let’s start exploring their relatioships and usage patterns. Oneplace where functions are applied is called mapping. Mapping is the act of applying a function to each element of a list, and returning a new, same-sized list containing the results. In general, the guts of a mapping function takes the following form:

In essence, what we are doing here is applying a converter function to the given item. Mapping is prevalent when dealing with collections, e.g., arrays, list and sequences. Because we have not studied list or sequences yet, let’s use arrays to illustrate how mapping works. To start, let’s define an array of floats from 1.0-10.0.

Now let’s write a function called map that applies a given function to a given set of floating point values – nums in our case:

// Imperative implementation – I don’t want to mix together recursion and
// mapping – I am trying to present one topic at a time as not to confuse
// the discussion.
let map fn (alist:float array) =

As you can see here, the function System.Math.Sqrt is applied to each element of the given array, in turn. The result of each function application is stored in a results array, which is returned by this function.

Mapping is such a common operation in functional programming that the F# libraries ship with efficient implementations. This means that we generally don’t need to forge our own implementations.

Let’s take a look at the Microsoft.FSharp.Collections.Array class again, relative to what is offers in terms of mapping. This following table was taken directly from the Array documentation found on the Microsoft Research site:

Don’t worry about the 'T and 'U notation for the moment. This is F#’s notation for generics, which we’’ will cover soon. For now, mentally replace 'T with integer and 'U with integer or float or a concrete type with which you’re comfortable.

To see how these functions work, let’s create an Array to hold the original values that we’ll map against. Instead of using zeroCreate to create our Array, we will use the more flexible init method, which enables us to create and initialize the array using a lambda function. Note that most of Array’s interesting functions are defined on the class itself (are static), and we access them via the Array.method syntax. On to the example:

Now that we have an array, we can apply a function to each element. Let’s compute the square of each element this time:

Notice here that we are applying a lambda function, whereas in the previous example, we applied a standard .NET function (System.Math.Sqrt). It doesn’t matter to F# whether the function is a lambda function or a standard function – it’s “all functions” as far as it’s concerned.

Something to note: the function you apply must be compatible with the target. In other words, if we were to replace fun n -> n * n with another function – one that expects, say, floats, like System.Math.Sqrt, F# would complain that it couldn’t apply a function that expects a float to a value of type integer.

Let’s finish off this section by providing examples of using Array’s various mapping functions. At their core, these functions all apply a conversion function to their input list and produce a new, resulting list. In F#-ese:

val evens : int array = [|0; 2; 4; 6; 8; 10|]
val odds : int array = [|1; 3; 5; 7; 9; 11|]
val sums : int array = [|1; 5; 9; 13; 17; 21|]

// Create an array of 6 evens, 0, 2, 4, 6, 8, 10
let evens = Array.init 6 (fun n -> n * 2)

val evens : int array = [|0; 2; 4; 6; 8; 10|]
val cube4 : int array = [|0; 0; 64; 0; 0; 0|]

let cubes = Array.mapi (fun index n -> if index % 2 = 1 then n*n*n else 0) evens

val evens : int array = [|0; 2; 4; 6; 8; 10|]
val cubes : int array = [|0; 8; 0; 216; 0; 1000|]

Folding

The next functional concept that we need to be familiar with is that of folding. Folding is the act of processing a data structure in some order as to calculate a single return value. Generally, the implementation of a folding function is recursive.

Typically, folding deals with a collective data structure, e.g., an array, list or tree, and a combining function, e.g., addition or merging. The combining function is applied is some systematic way to the structure, building up a single return value as it goes. This return value is often referred to as an accumulator, since it’s used to accumulate the results as the operation proceeds.

Because folding is a such common operation performed in functional programs, many of F#’s data structures ship with folding methods. Let’s look at a simple example method from Array.

The first line of code creates an Array that holds the integers 0-9. The next line uses Array.fold to apply a function to each element. Here again we see lambda functions, a.k.a., lambdas, used. The first parameter to the lambda, acc, is the accumulator – the value used to build up the final result. The second parameter is the nums array, the collection over which the lambda is applied. The 0 parameter is the accumulator’s initial (seed) value.

Folding, also known as reducing or consuming, comes in two flavors: folding left and folding right. Folding left means your operations begin at the left-most element and work their way right. In other words, they consume the elements from left to right. Folding right means starting from the right-most element and working towards the left.

The decision to fold left or fold right has a dramatic impact when either the data structure under consideration is non-linear, like a binary tree, for example, or when the function applied to the data structure is non-commutative, e.g., division or subtraction. In other words, order usually matters.

Note that the initial value supplied to a fold (either left or right) is always the first value used when the folding begins. A slightly more mathematical way to describe left and right folding is illustrated below:

Folding left: If the input function is f and the elements are i₀...i_N, left folding computes:
f (... (f s i₀)...) i_N..Here, s is stands for “state”, which is another way to think of the accumulator. If we consider our previous example, a left fold can be thought of as:

Folding right:If the input function is f and the elements are i₀...i_N, right-folding computes:
f i₀ (...(f i_N s)). Here again, s stands for “state”, which is another way to think of the accumulator. If we again consider or previous example, a right fold can be thought of as:

Before we look at another example, it’s worthwhile to quickly visit the fold function’s type as documented at Microsoft Research and via Intellisense. See if you can decipher it – if you can can, congratualtions - it’s confusing!

This type signature tells us is that fold is a function that takes 3 parameters and returns a value (the right-most ‘State).

· fold’s first parameter is a function. Let’s call this the lambda function. The lambda function is of type ('a -> 'b -> 'a) and itself accepts 2 input parameters, an accumulator or state (the first ‘State) and a value of some type ( ‘T). The lambda returns a value that is type-comptible with the first parameter (the second ‘State). In terms of the fold function, thi means that the accumulator and the return value of the lambda function have the same data type.

· fold’s second parameter is an initial state (seed value of the accumulator) (the third ‘State).

· fold returns a value that has the same type at the accumulator. (The first ‘State and the last ‘State, by definition, are of the same type).

In the next example, we create an array containing the integers 0-4. We then fold the list left, using addition, and fold the list right, using subtraction. The F# Array class names the right fold foldBack. Notice that fold and foldBack take their seed and list values in the opposite order.

Note that when you look at the documentation for the Array type, you may notice that Array supports both a fold family of methods as well as a reduce family of methods. The only difference between these methods is that with fold you can supply an initial accumulator value, whereas with reduce, you cannot. With reduce, the accumulator starts at 0. You can also use Array’s scan and scanBack methods to obtain the intermediary results as well as the final, folded value, as in the following example:

let scanl = Array.scan(fun acc item -> acc + item) 0 nums
// scanl = [|0; 0; 1; 3; 6; 10|]

Unfolding

Akin to folding, functional programming supports the concept on unfolding. Unfolding means generating a list or sequence of elements from an initial value, using a function. While Array does not support unfolding, F# ships with data structures such as List and Seq (sequence) that do. We will look at unfolding more closely when we study these structures.

Filtering

We are fast becoming steeped in functional concepts. Stick with me for a little while more, and you will be in a great position to not only get the most out of the rest of this book, but will be able to read and understand a good amount of the mainstream[11] functional programming literature. We take this opportunity to move on to filtering.

Filtering is the process by which you apply a function to each element of a collection, keeping the ones you want and discarding the others. The function you apply to the elements must evaluate to true or false – a Boolean. Functions like these - that evaluate to true or false - are called predicates. When you apply a predicate to an element in the collection, if the predicate evaluates to true, the element under consideration is appended to a new results collection. If the predicate evaluates to false, the element is skipped. This process continues until the predicate has been applied to all of the original elements. Note that filtering does not affect the original list (remember, functional languages don’t like side effects).

Zipping

While “zipping” is not a term your hear bandied about in functional programming, the concept surfaces often enough to warrant a quick discussion. Zipping is the process of combining two lists together pair-wise (like how the teeth of a zipper come together, sort of). Let’s take the following two arrays as an example:

To pair up (or “zip together”) numbers (nums) with their squares (sqrs), you can use Array’s zip function:

val z : (int * int) array =
[|(0, 0); (1, 1); (2, 4); (3, 9); (4, 16); (5, 25); (6, 36); (7, 49);
(8, 64); (9, 81)|]

The Array class, among other collections classes such as List and Seq, supports a small family of zip functions.

Pipelining |>

Now that we understand functions and how to work with them, let’s explore F#’s pipeline operator (|>), arguably one of the most important operators in the language. The pipeline operator (sometimes referred to as the forward operator) enables us to pass a value into a function in a natural manner. Let’s look at a simple example to start:

In the first line of this example, we define a function f that takes a single argument x and returns x * 2. The second line demonstates a traditional call site, whereas the third line demonstrates the use of the |> operator – the value 10 is provided as (or “forward to” or “pipelined into”) f as its first parameter. The |> operator is often used to build a chain of processing, that enables us to express program logic in the sequence in which we think about it. Let’s look at a slightly more complex example:

Using the pipeline operator, we can write this example a bit more elegantly and clarify what’s happening:

As defined, the pipeline operator is a binary operator, meaning that it expects two inputs: a value and a function (val |> func). As we can see from the body of the operator’s implementation, the operator applies the given function to the given value (func val). This simplicty turns out to be very useful and poweful and provides a mechansim with which we can express algorithmic intent naturally.

The pipeline operator is especially powerful when dealing with lists and sequences of values. It enables us to quickly and naturally apply a chain of ordered operations on each element of a collection. We will see examples of this when we study lists and sequences.

Using the pipeline operator vs. calling functions with paramters has a few advantages, namely clarity and improved type inference. The |> operator support the flow of type information from input objects to the functions that act on them.

Note that the pipeline operator only works with functions that support partial application. Remember that your function supports partial application if it accepts multiple inputs separated by spaces vs. a function that forces the caller to supply a tuple as an argument.

One more example should whet your appetite for using the pipeline operator. In the following example, we tap into the .NET libraries to capture all of the processes running on a machine and filter out those with the name “taskeng” (since I have a bunch of those running):

val processes : string array =
[|"OfficeLiveSignIn"; "iexplore"; "explorer"; "cvpnd"; "rundll32"; "smax4pnp";
. . .
"MSASCui"; "wmpnetwk"; "System"; "IAANTmon"; "Idle"|]

Note that F# also supports the backward pipe operator (<|) operator, used far less frequently than the forward pipe operator(|>). It passes the expression on the right side to the function on the left side.

Function Composition

A common operation in which mathematical (and programmatic) functions participate is composition, e.g., f(g(x)). F# supports function composition via the function composition operator (>>). Function composition enables us to design low-level, granular functions and piece them together in various ways to form more complex structures.

The >> operator is a binary operator. It accepts 2 function parameters, f and g. The final argument, x, is usually supplied later on, as in our example that defines the function h (above).

Note that F# defines a sister operator << that enables us to combine functions in the reverse direction, e.g., g << f is the same as saying f >> g. To be honest, I am not sure of its value or utility outside of writing obscure code such as: let result = f >> g << h (which is the same as writing (f >> g) << h due to F#’s associativity rules). Use this construct sparingly, as its makes your code difficult to understand (IMHO).

Partial Application and Currying

Earlier in this chapter, we saw examples of partially applying functions. For completeness, I’d like to take a moment and review partial function application and describe it in the context of another, related concept called currying.

Mathematically, currying is the concept of deconstructing a function of multiple parameters into a composition of several functions all of arity 1. This means that a function taking multiple parameters can be represented by a combination of multiple functions each taking a single parameter. When we call a multi-argument function with fewer arguments than it expects, we are partially applying the function and, in return, receive a function that accepts 1 fewer parameter – F# curries the original function and returns to us one that expects 1 fewer parameter. For example:

Here, f is a function that takes 2 parameters, x and y. g is a function that results from calling f with 1 of its 2 expected parameters. In other languages, like C#, this would result in a compilation error. In F#, however, calling f in this way, a.k.a., parially applying f, results in a new function, which we capture in g. The new function, g, takes the remaining parameter as input. In the last line of this example, we invoke g with a parameter of the expcted type.

At the end of the day, the distinction between partial application and currying is not particularly important, especially from the pragmatic point of view of F#. Whether you are “partially applying” or “currying” is largely academic. The two concepts go hand-in-hand. That said, the fundamental concept of being able to call functions with a subset of argments, and have new functions returned, is an important characteristic of functional languages, and is used to provide powerful, useful and elegant constructs like function composition and pipelining.

Closures

For some reason, the term closure always used to cause me anxiety. I don’t know why. I think it’s because, as a visual learner, I tried to picture what a closure is, and I couldn’t quite do it – until it “clicked.” For all those visual learners out there, I’m going to do my best to help define what closures are, and demonstrate why they are useful constructions.

A closure is a function with some values attached. Let’s illustrate this using an example inspired by this article:

In this example, makePowerFn accepts a single parameter, power, and uses it to create a new function, powerFn, which is returned to the caller. The newly created function has one variable whose value is fixed – or closed. The other variable, b, which represents the base number (the one that will get raised to the given power) is called a free variable, since it is still not bound to a value yet. It will only be bound to a value when the function is called. A free variable, in other words, is a variable awaiting substitution (being bound to a value sometime in the future).

So, when we invoke square 3.0 above, how can it work? F# must somehow store the value of power (in this case 2.0) in order for the function to execute properly. The entity that contains power bound to 2.0 is called a closure. As you can see from this example, partially applying a function in F# results in a the formation of a closure.

Closures are common in a variety of programming languages today. Closures are dynamically allocated data structures containing a code pointer, pointing to a fixed piece of code computing a function result and an environment of bound variables. A closure is used to associate a function with a set of “private” variable.

Closures are local functions that are generated by certain F# expressions, such as lambda expressions, sequence expressions, computation expressions, and curried functions that use partially applied arguments. The closures generated by these expressions are stored for later evaluation.

As you can see, closures are an important idea – they enable F# and other functional programming languages to support high-order functions, partial application, currying, etc.

Continuations

Yet another functional concept with which you should be familiar is that of continuations. A continuation is a mechanism by which the system can freeze the state of a function (or entire program) and resume it at some point in the future. When the function returns to the original caller, it preserves the state of its local variables. If you are familiar with C# iterators, a.k.a. generators, you get the idea of a continuation. In F#, continuations manifest themselves in the form of sequences (Seq), which we will study later.

Note that continuations are closely related to and form the basis of a style of programming called Continuation Passing Style or CPS. In this style of programming, functions do not return values per se, but pass their results on to the next function in a chain. Let’s look at a simple example. First, we’ll define a few functions and illustrate a typical call sequence:

After mul is called, m contains the return value, which is subsequently passed in to the addone function. If we were to re-write these two calls in CPS style, we would add another parameter to mul – a function that accepts the results of the multiplication and continues the calculation. Here is the same example written in a CPS style:

Now mul takes one extra parameter – a continuation function –and applies it when it’s done with it own calculation. If we wanted to extend the continuation, we could add a continuation function parameter to addone as well, ad infinitum.

Programs written in CPS style favor functions with continuation parameters vs. creating long sequences of stack frames.

Continuations are useful for storing function or program state and “continuing” the program or function sometime in the future – again, iterators and generators are common examples. Continuations are first-class citizens in some functional programming languages like Scheme and cross-over languages like Ruby. A thorough coverage of continuations is beyond the scope of this book, but you have enough of a flavor of what they are what they do to appreciate and understand them.

Lazy Evaluation

Another interesting and useful construct we use in functional programming is lazy evaluation. Lazy evaluation, in contrast to the default eager evaluation, enables us to delay the execution of a computation until the results are actually needed. In order to take advantage of lazy evaluation, we use the keyword lazy keyword around the expression we want to delay.

Using the lazy keyword tells F# to delay the computation. “Until when?” you might ask – until you explicitly force the evaluation using the Lazy.Force function defined in the Microsoft.FSharp.Control.Lazy namespace. When you call force on a particular lazy expression, the value is computed and the results are cached using a specific memoization technique. This causes subsequent calls to the Force function to retrieve and use the cached value, whatever it is, even if this means raising an exception. The following example shows the basic syntax and concepts behind lazy evaluation:

As you can see, the F# Interactive Console reflects the fact that calc refers to a lazy calculation – and is not yet evaluated. To force evaluation, we use the Lazy.force function:

Now that we’ve called force once for this lazy expression, F# has cached (memoized) the value. Subsequent calls will retrieve the cached value.

While this example demonstrates the fundamental idea, it fails to answer the oft-posed question, “Does lazy evaluation has any practical applicability? I mean, if you need the value from a computation, why bother making it lazy only to force it later on?”

Lazy evaluation makes possible the creation of lazy data structures. F#, for example, supports lazy lists and lazy sequences. They are lazy in the sense that they only compute their elements when needed, e.g., when the elements are needed by the program. If we take these types of data structures to their logical limits, we can see that lazy evaluation enables to creation of lists and sequences that hold an infinite number of items. This is not possible to do with traditional collection structures.

In addition, lazy evaluation makes certain types of behind-the-scenes optimizations possible. A compiler that understands “lazy semantics” can rearrange code for more efficient execution, compile away or optimize branches, etc.

Lastly, since you only pay for what you use, lazy evaluation can speed up program execution. For instance, imagine a scenario where you have an if…then…else clause, where the else expression consists of an expensive computation that only occurs once in a great while. In this case, you would make the else expression a lazy expression and force its execution only when the code path dictated it. Subsequent calls through the else clause would use the cached value, increasing overall throughput.

Operator Overloading

Since it is so closely related to functions, the last topic we’ll cover in this chapter is operator overloading. To understand operator overloading, you first need to understand that F# implements operators simply as functions – functions with odd, symbol-based names (remember when Prince changed his name to a symbol?). You can define new or overload operators on records and classes, as well as in the global namespace. Since we’ve not covered records or classes yet, let’s demonstrate both overloading an existing operator (generally a bad idea), and creating a new operator in the global namespace. But, first, a word from our MSDN sponsors on the rules:

You can overload all the standard operators, but you can also create new operators out of sequences of certain characters. Allowed operator characters are !, $, %, &, *, +, -, ., /, <, =, >, ?, @, ^, | and ~. In addition, : is permitted, but not as the first character. The ~ character has the special meaning of making an operator unary, and is not part of the operator character sequence.

When overloading an operator (or creating a operator using the rules as specified above), we use the general form:

inline, which is optional, tells the compiler that “this is a short method that should be expanded at the call site vs. generating a function and a call at the call site.” Use inline judiciously, as you can introduce code bloat. The symbols that define the operator appear in parens, and depending on the operator type – unary or binary – the operator takes one or more parameters. The function-body performs the work.

When F# resolves this function, it finds an overloaded instance in the global namespace that matches the infered types (5 and 6 are integers) – and selects it for exection. Since F# invokes our overloaded operator, the result of the addition is 17 vs. 11. As you can see, when you overload existing operators, you run the risk of introducing confusion – so be careful with your new found power.

Not as risky, but worth considering carefully, is introducing a new operator into the mix. You many want to do this for brevity or cognitive clarity, in particular in specialty applications like engineering, mathematics, data processing, etc. For illustrative purposes, we will define a simple unary (we know it’s unary because we use the special symbol ~ to make it unary) operator that takes a number n (a float) and returns it’s reciproal ( 1.0 / n):

We can also introduce binary operators. The following operator takes two integers and computes their greates common divisor (the largest integer number which evenly divides into two other integers):

Note that the operator is recursive, demonstrating a useful factoid – that operators are nothing more than functions with irregular names.

To build this operator, in fact, all I did was to take a standard function, previously named gcd, and replaced the name gcd with the operator symbols. Now I can apply the operator naturally:

We will look at operator overloading in the context of records and classes upon discussing these topics in a later chapter.

do Bindings

Let’s conclude this chapter by discussing do bindings, which are nothing more than a way to execute code outside the context of a function or let expression. I chose to introduce do bindings here to show how code can be exectued outside the context of any function. A do binding takes the following form:

The expression in a do binding must return unit. Code in a top-level do binding is executed when the module[13] is initialized. The keyword do is optional (which is odd, since the name of the constructs includes the word “do.”)

Attributes can be applied to a top-level do binding. For example, if your program uses COM interop, you might want to apply the STAThread attribute to your program. You can do this by using an attribute on a do binding, as shown in the following example adapted from the MSDN documentation:

open System // access .NET System namespace (covered later)
open System.Windows.Forms // access forms namespace

let form1 = new Form() // create a new Form
form1.Text <- "XYZ" // change window caption

[<STAThread>]                     // running in single-threaded apartment
do                                // “do something”
    Application.Run(form1)        // the thing to do

That’s really all there is to the do binding. We will revisit it again in Chapter 16, when we specifically discuss namespaces and modules.

Project Euler

Now that we have studied functions, you may want to look at an interesting project called Project Euler. From the website, we learn that:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

Many people have taken up the Project Euler challenge and have solved the problems using F#. At this point in the material, you are well on your way to being able to read and understand some of the solutions. By the end of the book, you’ll be in a position to tackle many of the problems yourself!

What You Need to Know

· Congratulations! You made it through a long, tough chapter filled with lots of new ideas and techniques. Understanding the terminology from this chapter will help you a greatly in understanding and appreciating the rest of the material in this book.

· Functions are values and have strict types, represented using typeA -> typeB, etc.

· Functions can be nested. Nested functions help abstract and encapsulate complex sub-sections of the function body.

· High-order functions are those that can accept functions as arguments and can return (resolve to) functions as output values.

· In F#, you can call functions and omit one or more arguments. This is called partially applying a function. When you partially apply a function, F# generates a new function (using a closure) that stores the bound variables and contains a list of the remaining free variables (the ones you omitted in the first place).

· F#, like its functional cousins, prefers recursion to imperative loops. Recursion can lead to stack exhaustion, if you are not careful. One common technique that helps prevent stack exhaustion is tail recursion, where you write your code in such as way as to prevent operations from needing to occur at or after the recursive call site.

· F# supports lambda functions which are functions with no name. These are sometimes called anonymous functions.

· Common functional operations that you see in F# and other functional languages include mapping, filtering, folding and zipping.

· F# uses the pipeline operator |> to send the results of an expression as input to another expression.

· F# uses the >> to compose functions (build up more complex functions from more primitive ones).

· Currying is a technique whereby F# takes a function with multiple arguments and turns it into a series of functions each taking a single argument. Currying and partial application are generally discussed in tandem. They are not the same thing.

· Closures are structures that have their own set of private, bound variables, one or more free variables, e.g., function parameters, and a function. They are created by F# in several cases, one of which is when you partially apply a function. We will look at other cases later.

· Continuations are structures that save state which can be retrieved and used in the future. Iterators and generators are examples of continuations.

· Lazy evaluation, a.k.a., deferred execution, is a technique for delaying a calculation until it’s actually needed. F# uses the lazy keyword in tandem with the Lazy.Force function to implement lazy evaluation.

[1] From here on in, I may use the programmer-accepted slang term parens as a shortened form of parentheses.

[2] Note that the functions being semantically identical only applies to single-parameter functions. As we will see, when your functions have two or more parameters, the use of parenthesis, while still optional, changes the semantics.

[3] At least, that’s what I would have expected.

[4] I say conceptually because for optimization reasons, F# may bypass true function generation in favor of a more expedient imperative implementation. See FastFunc<> for details.

[5] The structure that “remembers” the supplied parameters is technically referred to as a closure. We will cover closures later in this chapter.

[6] I know this all too well. When I first tried learning functional programming, most of the texts went straight to the programming constructs – I had no idea what anything meant. In part, my experiences motivated me to share what I’ve learned in this book.

[7] This implementation allows inputs < 0, which is technically not allowed for factorials. I use this implementation for simplicity only, as it works correctly for n >=0 and enables us to discuss recursion.

[8] If you are not old enough to know what a real chalkboard is, I can’t help you there.

[9] Although I hear a horse with no name can get you through the desert.

[10] Remember that F# uses ‘T and the like to express generics. We will cover generics in another chapter.

[11] OK, so “mainstream” may be a bit optimistic at this point; however, I think we will see a dramatic spike in the interest and use of functional programming languages in the next 3-5 years.

[12] Inline functions are functions that are integrated directly into the calling code. It is an optimization suggestion to the compiler.

[13] We will discuss modules and packaging in a later chapter.

Introduction