An Introduction to F# for Functional Programming

his series of articles addresses functional programming, the main concepts and differences compared to other paradigms, and how F# helps you get up to speed and produce results. This article quickly lays the groundwork and then guides you on translating and/or interfacing with your existing code.

There is a great story about a man who came to the king’s palace and claimed that he could answer any question. When no one could really challenge him the king pointed to a tree far away and asked how many leaves it had. The man took almost no time before he answered some exact and rather large number. How could anyone check that the man actually gave the right number? Well, the king and his advisors being smart fellows silently ordered a servant to run to the tree and take off 20 leaves, and upon his return asked the man once again to count the leaves. Just as before, he was quick to give another large number that was exactly 20 less than the first?after which no one doubted him anymore.

Apart from the implications in computational complexity?mainly that it is easier to design an algorithm to verify an alleged result than to come up with one that produces the right result?an important lesson is to think unconventionally and apply clever and well-founded ideas to produce success. Functional programming, when contrasted with other paradigms, is exactly like that: a handful of simple yet extremely powerful ideas put together that require a different way of thinking; one that may seem unconventional if you are a hardcore imperative programmer, but one that opens up new worlds and an unparalleled productivity when coupled with the right tools and technologies.

In February 2008, S. Somasegar, Microsoft SVP?Developer Division, announced that F#, Microsoft?s new functional programming language, will become a first-class citizen in the .NET ecosystem and a fully-supported language in Visual Studio. This synergy of simple-yet-powerful concepts, meeting the right platform and abundance of tools and technologies, opened the eyes of many developers. Microsoft?s announcement has helped F# gain increasing popularity and sparked the interest of professional developers.

What is F#?

F# lets you do imperative programming if you need low-level control, but after you master the functional way of thinking, you will find little use for this and will appreciate the more abstract code that you get in the functional style. In this article you will only see the functional and object-oriented features presented.

F# shares common roots with the so-called ML family of languages (SML, OCaml?taught in many universities and used for research, yet little known elsewhere) but has followed a different path since its inception in 2002 in a Cambridge Microsoft Research lab, under the direction of Don Syme?one of the main designers of .NET Generics and a key player in much of Microsoft?s programming language research.

F# is a functional, object-oriented language that compiles to run on the Common Language Runtime (CLR)?it is built around a small and powerful functional core language, and features a complete set of object-oriented extensions that enable it to work seamlessly with other .NET languages. F# combines the expressiveness of dynamic languages with the power of statically typed ones (in F#, every value has a well-defined type, be that polymorphic or not), which coupled with a powerful type system (the compiler tells you what you did wrong before you run your program) and type inference (no need to annotate your code with types) makes your F# code shorter, more elegant, easier to understand, maintain, and extend than other .NET languages.

Getting Started
F# operates in two modes: one that understands the standard, traditional syntax, and one that features a simplified, more concise syntax that uses fewer keywords and enforces certain formatting rules that reflect scoping via indentation. This latter mode is called the #light mode, and it is initiated by entering #light?usually on the first line of your program file. In the remainder of this article, you should turn on #light mode, as shown in Listing 1.

F# comes with an incredibly useful tool called F# Interactive, a top-loop that is available to you either as a standalone program (fsi.exe) or as a Visual Studio add-in (see Figure 1). To use the add-in, first you need to enable it, then you can activate it by highlighting parts of your F# code and pressing Alt+Enter to send the highlighted text to it. The code you enter or send to the add-in will be parsed, compiled, and evaluated on the fly?and you can examine return values and their types easily. You can use this interactive session to test pieces of your code, interact with it dynamically by entering arbitrary expressions, etc.

?
Figure 1. Running F# Interactive as a Visual Studio Add-in: Using the interactive top-loop makes your life much easier–no need for lengthy compilation-test-fix cycles; you can evaluate pieces of your code on the fly.

You can also use code completion (press the Tab key) to show available code alternatives at any time. If you are typing directly into the interactive session (on the command line starting with >) you can close a code block using double semicolons. This sends the given block into the interactive session, which responds with either an error message, or a value binding and its type.

Functional Basics?Types, Values, and Bindings
In a nutshell, functional programming helps you to better abstract your values and the way you operate on them. To accomplish this, you have?beyond the ordinary standard data types and classes?a handful of key data abstraction mechanisms:

  • Discriminated unions (these help you create closed data representations)
  • Tuples and records (these let you bundle data more easily)
  • Function types (that allow you to define and enforce signatures)
  • Polymorphic abstract data types (these let you express generic structured data)
  • Sequences (collections that you can work with on demand?for instance, you could create an infinite stream of random numbers and read as many as you like)

You can define these types in as little code as:

// A person has a name and an age.  Represented as a record.type Person = { name: string; age: int; }// A pair/tuple that represents a name and its validity.type NameValid = string * bool// A generic predicate type (a function that maps values to booleans).type 'a predicate = 'a -> bool// The following are equivalent:type IntList = int listtype IntList' = List// All natural even numbers represented as a (nearly) infinite sequence.let evenNumbers = seq { 0 .. 2 .. Int32.max_int }

The last code line is a value definition?binding a value to a name. Here it appears as a top-level binding (meaning on the module level), however let bindings can occur anywhere in your programs, making it easy to introduce local functions and definitions nested at an arbitrary level.

Functional programming treats functions as first-class values, just like any data value, so you can embed functions in any data structure and pass them to or return them from other functions. Such functions are called higher-order functions. This capability lets functional programming languages incorporate object-oriented features easily, because a class type is simply a record with some function fields .

Understanding Immutability, Closures, and Type Inference
A fundamental concept in functional programming is immutability: The values you create do not change. This is in sharp contrast to object-oriented or imperative languages where mutation via variables is omnipresent. Instead of mutating values, you create new mutated copies by replacing your ordinary imperative-style void functions that mutate their parameters in-situ with functions that return a mutated copy of their parameters. You may wonder: Isn?t creating new copies wasteful? Not quite, as it turns out the compiler is able to optimize much of the copy-then-mutate operations away by applying some clever tactics, which allows it to perform better in certain situations than imperative compilers.

Why do you need variables then? Strictly speaking, you don?t (unless you want to write imperative code). Consider the code segment below:

let printSumDoubled x y = printf ?The result is = %d
? ((x+y)*2)let _ =    let a, b = 172, 201    printSumDoubled a b    let a, b = 215, 347    printSumDoubled a b

The first line defines a function that doubles the sum of its two arguments and prints the result. Note how no type annotations were needed, the compiler figures out what parameters have what types by looking at how they are used. Here, adding x to y gives it away that both x and y must be integers (by default for arithmetic operators, unless you annotate the parameters otherwise). Another noteworthy piece is that you don?t have to parenthesize the formal parameters nor separate them by commas. You can do that, but in that case your function no longer takes two arguments but instead one tuple argument, and you need to change each invocation similarly to printSumDoubled(a, b). Don?t worry, the compiler tells you if you are passing too many arguments when calling functions, however, passing fewer gives you a nifty way to create closures?functions that carry their own state bag:

let printSumWithFiveDoubled = printSumDoubled 5

Here printSumWithFiveDoubled is a function that expects a single integer argument, adds five to it, then doubles and prints the result. It is basically an instantiation of the printSumDoubled function, and this becomes more apparent in the following equivalent definition:

let printSumWithFiveDoubled y = printSumDoubled 5 y

The let bindings in the above snippet simply combine individual assignments on a single line. However, under the hood there is a lot more going on. In the first line, the snippet matches the value (172, 201) is matched against the pattern on the left (a, b). Because that’s a straightforward match, it results in binding those numbers to a and b, respectively. Naturally, you could pattern match against arbitrary complex expressions and create numerous bindings at once (or none at all?as in the top-level binding to _ which simply means throwing away the value of the computed expression). Functions that seemingly return no value (those that are void in C#, for instance) have the unit return type, which actually has a single “no-value” represented as (). The preceding example ignores this empty value.

The key piece is understanding that bindings are different from variables in the ordinary sense: they are nothing more than names for certain values, and reassigning them to new values simply shadows the previous ones. In effect, the above code is equivalent to:

let printSumDoubled x y = printf ?The result is = %d
? ((x+y)*2)let _ =    let a, b = 172, 201    printSumDoubled a b    let newA, newB = 215, 347    printSumDoubled newA newB

Enhancing Your Types and Pattern Matching
Using type augmentations is an effective way to manage the functionality provided around your types (see Listing 1).

Type definitions usually go hand-in-hand with some fundamental control abstraction mechanisms that operate on the values that belong to those types: pattern matching (against the structure of a value?such as matching a tree with a certain shape, or a list of a certain size and content), anonymous functions (or so-called lambda expressions: functions created on the fly and without a name), and aggregate higher-order functions (that apply functions on enumerable data). For instance, in Listing 1, Seq.sumByFloat is a static aggregate function on the Seq type (the type representing all enumerable types, and for which seq is a standard type abbreviation, as used in the type definition for Drawing) that takes an anonymous function (that extracts the perimeter of a shape), applies it on all shapes in the drawing, and sums up the results to get an indication of the amount of ink needed for the drawing.

Piping and Understanding Common Aggregate Functions
You may wonder about the definition of TotalInkNeeded using the pipe ( |>) operator. This operator is defined in the F# standard library as:

let (|>) x f = f x

Being an infix operator, the pipe sends (pipes) its left operand to the right one, giving an elegant way to express a function call. This has at least two nice consequences: first, you can typically get by without having to parenthesize your arguments, second, you actually aid the compiler in type inference (as you are pushing type information from the left by supplying values of known types).

The sumByFloat method is a special case of folding, which is a more general functional pattern that takes a function and an initial accumulator and weaves them through a collection by applying the function with the initial accumulator to the first element, then with the result to the second, and so on, resulting in the final value of the accumulator. The F# standard library supports folding, mapping (applying a function to every element in a collection to construct a new collection with the resulting values), and iterating (visiting every element) on all generic enumerable types. These aggregate operations and many of the more special operations derived from them are the most heavily used tools in any functional programmer?s toolset.

And finally, test out your new types in an interactive session easily, using the code from Listing 1. For example, the following code creates 20 new shapes (using a sequence comprehension and piping the result to the Drawing constructor) then calculates the total ink needed to draw them:

> let a = seq { for i in 1 .. 20                 -> if i % 3 = 0 then                        Circle (20, 20, i)                     elif i % 3 = 1 then                        Rectangle (20, 20, 20+i*2, 20+i)                     else                        Shape.Square (20, 20, i) } |> Drawing;;val a : Drawing> a.TotalInkNeeded;;val it : float = 1123.840674

Conclusion
In this article, you saw some of the key functional programming concepts and how you can quickly get started using them in F#. You looked at some basic type definitions, simple, function, and structured values, infinite lazy sequences, and types with augmented members that used aggregate higher-order functions, lambda expressions, and the piping operator. You also created an enumeration of values representing graphical shapes using a sequence comprehension. In the next article of this series, you will learn about some of these features in detail and also about the more advanced functional constructs that can really drive your F# productivity curve.

Share the Post:
Share on facebook
Share on twitter
Share on linkedin

Overview

Recent Articles: