Change Your Thinking

---

Functional programming requires a different way of thinking about the architecture of your software as compared to imperative programming. The first order of business is to stop thinking in terms of statement-based programming and start thinking in terms of expression-based programming. This means thinking in terms of systems of definitions and what can be derived from what, rather than sequential cause and effect. It will lead naturally to thinking in terms of immutable objects rather than the (mostly unconscious) mutable programming we’re all used to. Expression-based programming and immutable objects have direct consequences for a successful functional programmer and the ease with which we think about algorithms in a functional programming language.

Expression-based programming

What makes an imperative language imperative? Earlier I wrote:

“In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state…imperative programs define sequences of commands for the computer to perform.”[26]

In the previous quote is the key word “statement”. “In computer programming a statement is the smallest standalone element of an imperative programming language…[Statements do] not return results and are executed solely for their side effects.”[27] Obviously, in modern imperative languages, statements can also return values but they don’t have to.

Conversely, “an expression-oriented programming language is a programming language where every (or nearly every) construction is an expression and thus yields a value…All functional programming languages are expression-based.”[28]

A statement implicitly says “trust me and do this, I claim it’s the right thing to do,” whereas an expression says “here’s a way to derive a particular kind of result.” We can see the difference from our earlier examples.

A C# statement:

An F# expression:

Void return in F#

In order to work with classes defined in the .NET framework, F# has to allow for statement-based programming and therefore allows a void return type. This opens a Pandora’s box of mutable functions; why would you call a function that returns nothing unless it has some side effect? So, for example, in C# we often write methods with a void return type:

Because F# is an impure language and needs to support void returns in order to work with the .NET framework and other imperative .NET languages, we can also write, in F# (FSI console):

We are told this is a function that takes a string and returns a “unit,” F#’s word for “void.” The side effect is that something is emitted to the console window (its state changes). One should mostly avoid writing functions that return “unit,” as these imply that the function has side effects. There are perfectly valid reasons, such as persisting data to a database, but of course that is a side effect!

Eager expression evaluation

“In computer programming, eager evaluation or greedy evaluation is the evaluation strategy used by most traditional programming languages. In eager evaluation, an expression is evaluated as soon as it is bound to a variable. The alternative to eager evaluation is lazy evaluation, where expressions are only evaluated when evaluating a dependent expression. Imperative programming languages, where the order of execution is implicitly defined by the source code organization, almost always use eager evaluation.”[29]

Statements behave differently in statement-based and expression-based programming. In a statement-based language, at least within a small context such as a block, in the absence of other control logic, statements execute sequentially in the order in which they are defined. On the other hand, an impure expression-based language like F# allows statements to be embedded in expressions. In this case, the embedded statement will execute at the time the expression is evaluated, whenever that is. This is often difficult to wrap one’s head around at first, and results in some interesting behaviors. For example, let’s say you have a function that prints something and returns a literal (FSI console):

Note how Hi! is emitted immediately—F# performs “eager” expression evaluation by default. Furthermore, when we later call the function, because the expression has already been evaluated, the printfn statement embedded in it will not execute and Hi! is no longer emitted.

Conversely (FSI console):

Here, Adding cannot be evaluated until its parameters have been supplied. Therefore we get the console message Adding… each time we evaluate at the call site with Adding 1 2 or Adding 3 4.

Statements embedded in expressions can lead to a lot of confusion, for example when using printfn for debugging purposes. The expression will evaluate as soon as it can, not necessarily in the order that you would expect, especially coming from an imperative, statement-based, programming language.

Expression-based programming has other nuances. There are two fundamental evaluation strategies for expressions: eager and lazy. Let’s say you want to evaluate some expression based on whether a value is true or false:

Notice how the expressions (Add 1 2) and (Subtract 5 4) are both evaluated regardless of which expression result we want. This can potentially affect performance, so instead, we want to explicitly use lazy expression evaluation, which is discussed in the next section.

Lazy expression evaluation

“In programming language theory, lazy evaluation, or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations…Delayed evaluation has the advantage of being able to create calculable infinite lists without infinite loops or size matters interfering in computation.”[30]

Note that lazy evaluation was introduced as a part of lambda calculus, which if you recall, is the foundation for functional programming, so it is interesting that F# employs an eager evaluation scheme. However, it does support explicit lazy evaluation. The ML language family, on which F# is based, historically used eager evaluation by default, because its properties are more easily provable and its performance is more predictable. In the Haskell.NET experiment that preceded work on F#, Don Syme and Simon Peyton-Jones encountered so much difficulty trying to get a good implementation of laziness by default on top of .NET’s fundamentally eager approach that they basically gave up, and turned instead to a language with the same eager bias as .NET.

Let’s modify the previous example slightly, changing how we call Compute by using the “lazy” type[31]:

Notice now that when we force the expression to evaluate, only the expression (Add 1 2) is evaluated! By the way, also notice how the expression 0 had to be “lazy evaluated” in the match statement; we must keep type consistency in all the return values.

Functional programming requires that you have an understanding of when an expression evaluates and, keeping that in mind, consider when you might want to explicitly use lazy evaluation to improve the performance of the code. Note that some functional programming languages, such as Haskell, use “lazy evaluation” by default.

Lessons

• Imperative programming is statement-based.
• Functional programming is expression-based.
• Avoid functions that return unit (“void”), as this is a serious indicator that you are not coding in a “functional” manner and that your function has side effects.
• Expressions evaluate “eagerly” in F#, so for performance reasons, you may need to explicitly instruct the compiler that you want lazy evaluation.

Think immutable

It can be very difficult to learn how to think in terms of an immutable world. Things in everyday life are mutable. When we get in our car to drive somewhere, we turn the engine on. When we arrive at our destination, we turn the engine off. We are clearly changing the state of the car. We do not “copy” the car so that we now have one car with the engine off and another “identical” car but with the engine on! We live in a stateful world and one of the fundamental characteristics of things in our world is their state.

On the other hand, mathematics and logic deal primarily with immutable things, so functional programming can benefit from being much closer to natural ways of working in math and logic. Database design and significant areas of digital logic design also work with immutable definitions. Immutability gives us enormous power to reason about behavior of programs from a compile-time perspective—power to potentially know and be able to prove that a program is correct. Scientific understanding of the world is, after all, based largely on mathematics. To have a scientific understanding is to be able to explain outputs in terms of inputs, without magic or unfounded assumptions, just like in functional programming. Much of the work of developing a program or scientific theory is formalization—not so much writing code in a syntax, as getting from a vague understanding to a sharp one.

Shifting to a concept of immutability can be mentally difficult, but there are certain concrete structural things that you can do when writing functional code that help to make immutability more automatic. These are:

• Reduce encapsulation by creating associations explicitly as maps.
• Create smaller functions that do just one thing.

Reducing encapsulation

Thinking in terms of immutability means changing how you think about encapsulation. Often, we use encapsulation to collect many different concepts, or attributes, under a single umbrella. In imperative programming, this often appears reasonable but eventually leads to entanglement and complexity. In a functional programming environment, encapsulating seemingly related but actually distinct concepts creates undo “noise” in a given type and makes it difficult to work with immutable objects. What we need to do instead is tease apart the associations, using separate objects to interrelate them. Among other positive effects, this makes working with types much easier because a type doesn’t include attributes that fall into the “has a” relationship. A type should always express exactly what it is (that is to say, what defines it), not what it has (that is to say, what things are associated with it).

Think relational database architecture

The idea of “what defines an object” has its equivalence in database design and the concept of a unique key—given a table, each record is defined by what fields make that record unique. Yes, there may be other attributes, but the salient point is that you can always identify the unique record by its unique key. The other fields in the table can’t do this. This helps us identify core types in functional programming.

Another key aspect of database architecture is that associations are represented as separate tables through the use of foreign keys. When reducing encapsulation, think about how you would represent the class in a database. What are the separate tables you will need, and how are they associated? When you have gone through this exercise, you will be ready to implement the types correctly in F#.

Another key aspect of good database architecture is normalization, specifically, not repeating the same data. We will also use this practice as a guideline for creating better F# code.

An example of reducing encapsulation

We’ll work next with an example and see how we can relate this new way of thinking to a very imperative implementation of the C# class User:

This simple class serves the purpose of illustrating mutability and side effects in a typical imperative style. This class requires some rework to be a well-behaved set of F# types and functions. Note how even in the use of the terms types and functions, we are decomposing the properties of a class into their constituent components. If implemented as an immutable object in F#, it would require cloning all the properties, including the collection of roles. This is something we want to optimize when a user’s configuration changes.

If we apply our “design a class like you would design a database” principle, we can conclude that:

• A user is defined by the combination of username and password or email and password, so the properties username, email, and password are a natural grouping. The additional roles collection is not characteristic of defining a user and should be removed from the type that defines User.
• Roles can also be considered a foreign key association, giving further motivation to the idea that it should be its own “first class” type and that a separate type that manages associations between users and roles is needed.
• This also “normalizes” the data by eliminating the duplication of role names across many users.

We can now define our types in F#, starting with User:

We also need a simple UserRole type:

And lastly, a type that associates a user with a list of roles:

We can now instantiate a user with a couple roles, for example:

Notice that by reducing the complexity of the encapsulation illustrated in the C# User class, we have created three different types. Granted, there is nothing that prevents us from doing this in an imperative language; it’s just that we typically gravitate towards complexity when working with classes. The types we’ve created here are much simpler structural compositions, which ultimately facilitates being able to do more with these simpler structures. Using these new types, we will next explore the “functional” way of operating on these types in an immutable context.

Lessons

• Reduce object complexity by decoupling the implicit associations of types.
• To do this, think more in terms of a normalized relational database architecture:

• What are the fields that uniquely define a record?
• What are the associations between records?

• Create small types (records), as these are more easily associated with other types (records).

Reduce complex functions

Let’s look again at the SetPassword method in C#:

This method is very simple, but from a functional programming perspective, it has several problems:

4. The encoding protocol is hard-coded into the method body—anyone using this method cannot change the encoding protocol.
5. The hash algorithm must be known when the method is called.
6. The method does not return the hashed password; it instead sets the internal field to the resulting hash value—a side effect.
7. This method cannot be extended—for example, adding password salt—without deriving from the entire class.
8. Since the programmer didn’t specify that this method is virtual, the method in fact cannot be overridden, forcing the programmer to take more drastic measures to create the desired function. The code as written is therefore not very extensible, and any workarounds that the next programmer creates probably results in code duplication, introduces potential errors if the programmer changes the original method, and contributes to code brittleness.

Certainly the last point can again be easily addressed by better OO design, and it is certainly possible to write bad functional programs as well; however, functional programming tends to promote the thinking “do one thing only.” We therefore decompose the SetPassword method into two functions.

For the following examples, we need to include a couple .NET namespaces:

We can still define the encoding function as:

And the hash computation algorithm as (one way of doing this is):

Because we’re working with a .NET base class (HashAlgorithm) that has many overloaded Compute methods, we have to specify the type information for the class containing the Compute method and the parameter type.

Another way of defining this function is to specify the required types in the parameters of the getHash method:

This second form allows the compiler to select the correct Compute method because it already knows the type for hashAlgo as well as the type for bytes.

By separating the C# method into two simpler functions, we are moving toward working with more core behaviors, giving the programmer the ability to change the behavior of the program without running into the problems I’ve listed previously.

We can define a third function, which, given a password, computes the password hash:

And we use it like this (FSI console):

Not only is this a fairly ugly F# function, but it still has an imperative “feel” to it. A more functional approach would be to use function pipelining.

Lessons

• Create functions that do one thing and one thing only.
• Smaller functions are more composable (more on this next).
• Smaller functions make it easier for you to change the behavior of the application without breaking other parts of the code.

Function pipelining, partial application, and function composition

While it can be considered a mantra to write smaller functions, even in imperative languages, at the end of the day all those little functions must still be put together to do something bigger. Imperative programming promotes a very tight coupling of “sequence” and requires that all the information be available right now in order to execute the sequence of instructions.

Functional programming has several different ways of putting together all those little functions:

• Function pipelining: By supplying the first value, the resulting value(s) of one function feed directly into the next function, resulting in a final value.
• Partial application: Creating a function that has some of its initial parameters bound to values, allowing the rest of the parameters to be supplied later.
• Function composition: Creating a function that is composed of several other functions, where, similar to pipelining, the resulting value of one function supplies the first parameter of the next function.

Function pipelining

One of the important features in functional programming is the idea of a function pipeline. “The pipeline operator, |>, is one of the most important operators in F#.”[32] The pipeline operator “can be thought of as threading an argument through a series of functions.”[33] Nested function calls can be difficult to read. A function pipeline with n stages provides an easy, left-to-right readable alternate syntax for a nested series of function calls n levels deep.

If we rewrite the previous F# code using the pipeline operator |>, the code becomes more readable:

Here we are telling the compiler:

9. Create a function called pwdHash that takes a single parameter, which is inferred to be a string.
10. Call the function encodeUTF8, passing the password.
11. The evaluation is passed to the function GetHash, along with the parameter new SHA1Managed().

Partial application

“In computer science, partial application (or partial function application) refers to the process of fixing a number of arguments to a function, producing another function of smaller arity.”[34] (“Arity” means the number of arguments that a function accepts.)

We can further “functionalize” the previous code by deferring the hash algorithm, simply by creating a partial application:

Here, we are defining a function that takes a password but returns a function that expects a hash algorithm to be provided. However, this also requires that we switch the parameter order of the getHash function, which is why I previously called it getHash2 (more on this later):

Why? Because we are providing the first parameter in the pipeline and expecting the caller to later provide the second parameter, which is the hash algorithm.

In the pwdHash2 function, we are “piping” the password parameter into the byte encoder and then “piping” the resulting encoded byte[ ] value into the getHash2 function, which returns a function that expects an encoding algorithm and returns a byte[ ] of encoded values.

We use it like this (FSI console):

Observe how we created the partial application pwdHash2 that, on evaluation, encodes our password with UTF8 encoding, but lets us defer the selection of the actual hash algorithm. We assign the encoded password by piping in the raw password string, completing the function application by providing the hash algorithm object.

The syntax of this is a little messy because we’re mixing in .NET objects rather than working with pure F# functions. However, I believe this represents the real world of what you’ll be dealing with when programming in F#, so I’d rather illustrate this syntax than a pure F# implementation. It’s all part of thinking functionally but realizing that you still have to work with imperative style frameworks that don’t support function pipelining and currying.

Lessons

• When you write functions, consider which parameters are most likely to be partially applied and put those parameters first.
• If the programmer didn’t provide the parameters in the order that you want, write a function that flips the parameters around that you can use to create a partial application function.

Revisiting function pipelining and introducing tuples

We can now consider how to add different behaviors, for example, adding some “salt” to the password. This further illustrates how the behavior of our application can be easily changed as a result of simple, composable functions. First, let’s look at the encoding function this way:

We’ll be appending an encoded salt before passing the result to the getHash2 function:

Notice the ||> operator. This operator takes a tuple and pipes it to a function that takes two parameters. The tuple is constructed from the password and salt:

Next, it’s piped into the Array.append function:

The result is then piped to the getHash2 function with the desired hash encoder. If you’re curious, there’s also the triple pipeline operator |||>, which takes a tuple of three values and passes it to a function that takes three parameters.

Function composition

Pipelining requires that the input values are provided to “initialize” the pipe. For example, this function:

Is rewritten using pipelining as:

However, we may not know the value, and this is where function composition, using the >> operator, comes into play. The example used earlier:

Can be rewritten without the initial value of abc:

Here we have created a function pwdEncoder that is a composition of the encoder and hashing functions. We use it like this (FSI console):

Or like this:

Lessons

• In order to take advantage of functional composition, it’s best to have functions that take only one parameter.
• Your functions in a composition most likely will be partial function applications!

Functions vs. literals: the key difference between pipeline and composition

Function composition, as the name implies, is a composition of functions that is itself a function. First-class functions are a kind of value, but values in general are not functions. So for example, I cannot write:

The compiler complains that it is expecting array1 to be a function, but instead it is an int[ ]; in other words, a literal.

We can, however, write:

We can do this because encodeUTF8 is a function, not a literal, and we can use functions anywhere we need values. Once we supply the function t1 with the initial literal value abc, then t1 evaluates, passing the result of “abc” |> encodeUTF8 to the Array.append function, which has already received as its first parameter the value resulting from evaluating encodeUTF8 “salt”.

Consider this partial function application in which we do not provide the encoded salt parameter:

Which can be used as follows:

Notice how we are combining pipelining (starting with an initial value) with function composition (a function that encodes a value and passes the result to the partial application of the append function.) It is very important to know whether you are working with a literal or a “function as a value,” as this guides you on how to work with function pipelining and function composition.

Partial application and pipelining

It’s also important to understand the interaction between partial application and pipelining, as there can be unintended consequences.

Given (FSI console):

Here, getHash(new SHA1Managed()) returns a partial application function, having had the first parameter “fixed” or “bound.” Having been supplied the first parameter, this leaves the byte[ ] parameter to be supplied by the pipeline.

Compare this with:

Here we can clearly see that pipelining tries to supply the first parameter, but since getHash is a partial application in which no parameters have been supplied, it fails with a type mismatch because the pipeline is attempting to provide the first parameter, which is of type HashAlgorithm, with a byte[ ]!

One correct usage would look like this:

Value confusion

It becomes clear from the previous code that the partial application getHash(new SHA1Managed()) takes precedence over the pipeline operator. When we didn’t correctly create the partial function application, we were able to identify this problem during coding because the getHash function has parameters of different types and the compiler or IDE told us we had a problem. However, if the parameters are the same type, we can easily create computational errors that are only discovered at run time. We can illustrate this point more clearly with the following code (FSI console):

Because F# evaluates from left to right, it would seem logical that in the code 5 |> Sub 3 that 5 is assigned to x, resulting in the partial function application Sub 5, and then 3 is applied as the y parameter, resulting in an answer of 2. This is not the case! If we want this behavior, we need to specify that 5 |> Sub is to be evaluated first by parenthesizing the expression:

Here we clearly see that the partial application Sub 3 takes priority, making 3 the x and 5 the y.

Putting it all together the right way

The previous code still misses what we want to accomplish:

• We want to be able to specify the encoder and hash algorithm to be used outside of the actual hashing function—in other words, we want to abstract out the actual encoder and hash algorithm that the application might want to use.
• We’d like to be able to cleanly append byte streams so we can work with passwords and salt.

Using everything we’ve learned about function composition, partial function application, and function pipelining, we’re now ready to put together a much cleaner implementation, demonstrating (hopefully) the unique features of F# and functional programming in general.

Implementation

We start with the two functions that interface to the .NET API:

Next, we want to generalize the idea of appending byte arrays, so we’ll write a general purpose “encode string and append” function:

The reason I call this encodeStringAndAppendFunction is because, when given an encoding algorithm that converts a string to a byte[ ], it returns a partial function application—only the first parameter of the Array.append function has been supplied.

This allows us to chain together encode-and-append operations. We can do this in separate let statements, concluding with the final “append an empty array.”

Or we can put the entire expression inline:

Important: Notice that I am using the right-to-left composition operator, <<. This is because I would like my salt be appended to my password, and therefore the salt must be the second parameter of the Array.append function.

For our purposes, we will create a function that simply encodes a password and salt:

Here we use the double-pipe operator to provide the encoder along with the password, and then apply it again with the salt, creating a function composition that evaluates when we pipe in the empty array, which we’ll see next.

What’s nice about this function is that it provides a clear template for how to extend the function with additional strings that we might want to add to the byte[ ] before it is hashed. Later on, in the discussion on recursion, we’ll generalize this even further.

We then create a function whose parameters have been carefully arranged such that it is suitable for partial function application:

• Because the encoder and hash algorithms probably won’t vary for a set of passwords and salt, we want these to be the first parameters.
• Furthermore, the encoder and hash algorithm are always “together,” so we can specify them as a tuple rather than in curried form (separated by white space).

We can use this function directly (FSI console):

But because I’ve judiciously placed the encoder-hasher tuple first, I can create partial function applications with different encoding and hashing algorithms (FSI console):

We now have a very flexible system of hashing salted passwords with different encoding and hashing approaches, using partial application to create a re-usable hashing function.

Lessons

• Wrap .NET functions so that you can use partial application constructs.
• Put the invariant parameters first in a function so that the function is suitable for partial application.
• Partial application is very powerful, allowing you to create function compositions that reveal useful patterns, giving you clues as to further abstraction for creating robust applications.
• Partial application is one of functional programming’s “reuse” strategies. Code for this strategy.
• Not to be repetitive, but make your functions as small as possible!

Recursion is the new iteration

In imperative languages, we often (not as often anymore, but you still see it) write iteration like this (C#):

With the advent of lambda expressions, we can write (C#):

Or, if you wish to implement an extension method:

All of these C# examples require mutability—the value of sum is being incremented and is a side effect of the computation expression.

Recursion is used in F# to avoid mutability. Yes, we could write this example in F# as (FSI console):

Notice we have to explicitly state that the sum is mutable.

Instead, the “functional programming” way of working with iteration is to use recursion (FSI console):

This is an example of tail recursion. “In computer science, a tail call is a subroutine call that happens inside another procedure as its final action; it may produce a return value which is then immediately returned by the calling procedure. The call site is then said to be in tail position, i.e. at the end of the calling procedure. If any call that a subroutine performs, such that it might eventually lead to this same subroutine being called again down the call chain, is in tail position, such a subroutine is said to be tail-recursive which is a special case of recursion. Tail calls need not be recursive—the call can be to another function—but tail recursion is particularly useful, and often easier to handle in implementations...Tail calls are significant because they can be implemented without adding a new stack frame to the call stack...[I]n functional programming languages, tail call elimination is often guaranteed by the language standard, and this guarantee allows using recursion, in particular tail recursion, in place of loops.”[35]

There are two things that make tail recursion difficult coming from imperative programming:

• How do you convert a loop into a tail recursion?
• How do you know you’ve implemented tail recursion correctly?

Converting loops to tail recursion

One could roughly put tail recursion into two categories:

• Those in which an “accumulator” needs to be threaded through the recursion.
• Those that operate on lists without needing an accumulator.

The previous example illustrates how to manually thread an accumulator through a recursion. The F# list classes have many functions that do this for you automatically. For example, one would normally have written (FSI console):

Or:

These examples take advantage of the List.fold[36] and List.reduce[37] functions. Realistically though, sometimes multiple accumulators are required, or the operation on each item in a list may require a manual tail recursion implementation for some reason.

The second kind of operation, operating on a list without needing an accumulator, often works with the “head” and “tail” of a list. For example, simply printing the numbers in a list, we use a match statement to test for an empty list; otherwise we use the syntax hd :: tl to extract the head of the list and the remainder of the list, the tail (FSI console):

As a side note, notice that since this function has a side effect (it merely prints numbers to the console), when the list is empty, we are returning unit, expressed by the “()”.

Implementing tail recursion correctly

“‘Tail Recursion’ is a special recursive function which does not [include] any other execution after the recursive call, meaning there is no ‘pending operation.’”[38]

If we use dotPeek to decompile the IL generated by the previous function, we see that it is implemented as an iteration with a while (true) loop:

If instead we have a pending operation (here created by printing the head last):

Besides printing the list in reverse order, we note from the decompiled code that the compiler has implemented it as a recursive call:

This is not the desired implementation, as it is susceptible to stack overflows and will perform poorly because of all the stack pushes and unwinding that will occur.

In order to implement tail recursion, the recursive call must be the last operation in the code branch of the function or must return nothing (unit) or a value. Sometimes this can be difficult to implement, which is where the interesting subject of continuation passing style (CPS) comes up.

You can read more about CPS at http://codebetter.com/matthewpodwysocki/2008/08/13/recursing-on-recursion-continuation-passing/. We’ll be looking at CPS a bit more in Chapter 3.

For and while: when to use iteration

The primary purpose of for and while statements is to iterate a fixed number of times independent of the data being processed, or to perform a process forever (or typically for the application’s lifetime). F# provides three different looping constructs:

• for … to[39]
• for … in[40]
• while[41]

For example, either of these constructs makes much more sense:

When compared to a recursive implementation:

With the recursive implementation it’s much clearer what it’s doing and when, but it becomes much harder to answer the question, “How many times does this loop iterate?” However, except for a fixed number iterations (data independent), one should consider carefully the advantages of using recursion over iteration.

Why use recursion?

Recursion has the advantage of being more mathematically expressive—it declares exactly what conditions result in a recursive call and it declares exactly what ends the recursive call. It also explicitly states what computation is performed during and at the conclusion of the recursion. For this reason, recursion can actually be easier to read than iteration, which may have control logic such as a return or break embedded somewhere in the iteration, as well as multiple exit processes. Using recursion, these behaviors are almost always either placed outside of the recursive call or are made very explicit, usually by threading state through the recursive call.

Using recursion with imperative collections

One might think that another good use case for iteration is working with imperative collections. For example, this data reader seems perfectly fine to implement with an F# while…do construct:

However, it is just as easily implemented with recursion, which in the opinion of the author has a very nice explicitness to it, especially with regards to closing the reader, which the programmer may otherwise forget (and still might in the F# implementation, but I think it does make it more explicit):

We’ll use the database reader example next when we look at working with collections.

Lessons

• Learn the functions in the Collections.List module,[42] as these will greatly reduce the amount of recursion code you have to write yourself.
• When thinking about recursion, ask yourself, “Do I need to thread an accumulator through the process?” This affects the signature of the recursive function.
• Make sure the last thing your recursive function does is call itself—there should not be any pending operations. Otherwise the compiler will not implement the recursion as a loop and you will incur the overhead of function calls and stack usage and possibly cause a stack overflow.
• Tail recursion is so-called not because of the head :: tail syntax when working with lists, but because the recursive call is in the “tail position” of the function.[43]

Collections

In order to ensure that the programmer doesn’t accidentally mutate a collection, F# provides a completely separate implementation of collections. In C#, we have the System.Collections and System.Collections.Generic namespaces. F# gives us the Microsoft.FSharp.Collections[44] namespace, which implements immutable List, Array, seq, Map, and Set collections.

Building collections

When building a list of items, the new item always appears first when using the “cons” (prepend) :: operator. The reason is straightforward once you think about it. Given a list:

If we were to append an item to this list, we would be modifying the current list: the “next item” for the entry 3 would need to be modified to now link to item 4.

Instead, we have to write:

This ensures that list doesn’t mutate. In order to append an item to a list, we have to use the concatenation operator (@) and put our new item into a second list:

This can be a bit confusing to work with when coming from the mutable collection classes in the System.Collections.Generic namespace, where we can operate directly on the list in a willy-nilly fashion.

The real reason for recursion

Let’s look at how we can go about creating a list of records using the query I created previously. Here’s the record:

We will first look at the iterative code in the previous section that reads the People data.

Notice in the previous code that the list variable must be mutable when we use iteration. Iteration requires constantly pre-pending (we could have used concatenation also) the list with new items and updating the variable that holds the list, forcing us to use a mutable list variable. This is functional programming code smell.

The only way to solve this is with recursion where the list that we’re building is threaded through the recursive calls:

Here we see why recursion is so important when working in a functional programming language—it allows us to preserve immutable behavior by threading the list through the recursive function calls, such that each new call is actually a new list. It can take some time getting used to constructing collections in an immutable manner, and recursion plays a significant role in that process. I would strongly recommend that you take some simple iteration code samples from your favorite imperative language and practice rewriting them in an immutable, recursive manner.

Working with collections: map, reduce, and filter

Working with immutable collections requires a certain degree of mental gymnastics. Recursion is one of the fundamental tools in the programmer’s toolkit for managing collections. The other toolkit items are the three fundamental operations on collections: map, reduce (equivalent to “fold” in some other languages), and filter.[45]

• Map applies a function to every item and returns a list of the results of each function call.
• Reduce applies two arguments cumulatively such that the result is a single value determined by the provided function.
• Filter returns a list qualified by a test function that returns true or false.

We perform these operations implicitly all the time in imperative programming. With functional programming, there are specific functions provided by the collection classes that implement the map, reduce, and filter behaviors. With the advent of C# 3.0, we also have these functions available to any collection that implements IEnumerable as Select, Aggregate, and Where, respectively, and you might have already used them in LINQ expressions, for example.

Regardless of your familiarity with them in imperative .NET languages, you should take the time to think about your list manipulations in terms of these three behavior patterns. You will frequently see them combined using pipelining to return complex computational results.

Using the data returned from this SQL query (I removed the “top 5”):

 We can see how we can apply filtering, mapping, and several other list operations:

Here we are pipelining several operations:

• Filtering only the last names that start with Cl.
• Mapping the record to a comma delimited last name, first name string.
• Sorting by the resulting string.
• Selecting only the unique names.
• Converting the sequence back to a list.

This is a nice illustration of the readability and conciseness of F#.

Lessons

• Recursion is a key tool when working with immutable collections.
• Learn the map, reduce, and filter functions provided by the F# collection classes.

Some further, minor points

Be expressive

The reader should not have to worry about “how” you are doing something as long you express “what” you are doing adequately. The problem with imperative code is that the “what” is often lost in the “how,” and functional programming can help to bring that to light.

Use Collection features such as iter—use lambda expressions!

Return something!

Even if you must write a function that results in a mutation or side effect and ideally you don’t need to return anything, consider what you might want to return so that you can take advantage of function pipelining. Typically, one simply returns the same parameter that was passed into the function. However, since you don’t know how the caller is going to use your function, program “functionally” so that the caller is not limited by your function’s implementation.