Phillip Trelford's Array

This month F# became the first functional programming language to hit the top 20 of the TIOBE Programming Community Index:

The recent rise in popularity of F# comes as no surprise. Apart from being a nicely designed language, F# is available in the latest version of Microsoft's Visual Studio (2010).

Functional programming is by no means a new concept in fact it has its roots in the Lambda Calculus developed in the 1930s. The first popular functional flavoured language Lisp was developed in the 1950s and ML, a language that F# owes much of its syntax to, was developed  in the 1970s.

Some claim that functional programming concepts appear unfamiliar, in fact they are all around us, in Javascript, C#’s LINQ and even spreadsheets.. If you’ve ever written formulas in a spreadsheet then you’re already familiar with some of the principles of functional programming. The key building blocks of a spreadsheet are cells containing functions and values.

Over on Developer Fusion there’s a tutorial that demonstrates some key functional concepts while actually building a spreadsheet application in a couple of hundred lines of F#:

• Functional Cells: A Spreadsheet in F#

If you already have some F# or functional programming then why not give it a try, otherwise you might want to read on.

Functional Programming Basics

The following concepts are considered specific to Functional Programming:

• Pure functions
• First class and higher order functions
• Pattern matching

Pure Functions

Pure functions are functions that are free from side effects. That is pure functions always return the same result when called with the same parameters. Formulas in a spreadsheet hold this property.

First class and higher order functions

Functions are said to be first-class when they can be treated as first class objects. So like objects, functions can be passed as arguments to other functions, returned as values, assigned to values or stored in data structures.

Higher order functions are functions that take functions as their arguments. For example the LINQ Select method is an extension method that takes the function selector as a parameter:

public static IEnumerable<TSource>

    Select<TSource, TResult>(

        this IEnumerable<TSource> source, Func<TSource, TResult> selector)

Higher order functions are often used with anonymous functions as arguments. In the following line of code an anonymous function is passed to the Select function:

var squares = (new[] { 1, 2, 3 }).Select(n => n * n);

Support for higher-order and anonymous functions has been available in C# since 3.0 and will be available in C++ in the C++0x standard. They are also an integral part of JavaScript.

Pattern Matching

Many C based languages including C# supports basic pattern matching in the form of switch statements, matching against integral value and string types. In F#, and other ML based languages, a match statement is used instead:

Functional programming languages allow pattern matching on types too. The following C# and F# code snippets are equivalent:

In the code above the shape type is defined using an F# discriminated union, also known as algebraic data types in other functional languages like Haskell and Miranda. You can think of the type Shape as defining an empty abstract base class, and Line and Square as classes that inherit from the base class, just like the C# code to the left.

Note: The ‘*’ character in “Line of Point * Point” means “and”, i.e. a Line of Point and Point.

See Tomas Petricek and I implement the code above in the following video:

Starting F#

If you have Visual Studio 2010 then you already have F# installed, just start a New Project:

If you’re on Windows and don’t already have Visual Studio, you can also download the Visual Studio 2010 Shell for free and then install F#.

If you’re on Linux or Mac then you can use F# with Mono with MonoDevelop or Emacs. Or you can even edit F# code in your browser at http://tryfsharp.org.

F# Interactive

You can try out your F# code immediately in Visual Studio using the F# interactive window. Just highlight the code and presss ALT+ENTER

F# Basics

F# is a statically typed functional programming language on .Net that aims to minimize the ceremony of coding. F# functions are first class so they don’t need to be defined inside a class and type inference means that most of the time the compiler will infer the types of objects for you.

Values

The let keyword is used to define values with type inference (like the var keyword in C#).

Values in F# are by default immutable (constant):

let alwaysTrue = true

Values must be marked explicitly as mutable if you want to be able to change them:

let mutable variable = 1

Functions

The following function uses a conditional expression, with its type is inferred as a function that takes a bool and returns a bool:

let Not value = if true then false else true

Pattern Matching

The Not function can also be written as a match expression:

let Not value =

    match value with

    | true -> false

    | false –> true

This is the shorthand equivalent using the function keyword:

let Not = function true -> false | false -> true

Pattern matching can be also be used to match against tabular values:

let And p q =

    match p, q with

    | true,  true   -> true

    | true,  false  -> false

    | false, true   -> false

    | false, false  -> false

One of the nice things about F# pattern matching is the added type safety. If a case is missing then the compiler gives a warning.

Discriminated Unions

A discriminated union is a type whose values can be any one of a set of types. You can think of it being like an enum in C# where each item has a specified type.

Option Types

The Option type is a simple example of a discriminated union, and it’s one that’s built into F#:

type Option<'TValue> = Some of 'TValue | None

The Option type is used when an actual value might not exist in which case it is specified as None, otherwise it is Some value. In F# the Option type is preferred over the use of null, and this helps remove a whole class of bugs.

Simple Parsing

Parsing a Spreadsheet formula based on whether it starts with an equals (‘=’) sign:

let parseFormula (s:string) =

    if s.StartsWith "=" then Some(s.Substring(1))

    else None

Parsing a decimal string value:

let parseNumber s =

    match Decimal.TryParse(s) with

    | true, n -> Some n

    | false, _ –> None

For a primitive spreadsheet we could define cell values as being either formulas or numbers:

type value = Formula of string | Number of decimal

Now we can match a text string with the parsers for formulas and numbers:

let parse s =

    match parseFormula s, parseNumber s with

    | Some formula, None -> Formula formula

    | None, Some number  -> Number number

    | _, _ -> invalidOp "Unknown value type"

Active Patterns

Active Patterns are defined inside banana brackets, i.e. ‘(|’, ‘|)’. An Active Pattern is a function that can be used actively inside a pattern matching expression.

The following Active Pattern returns whether a number is Odd or Even:

let (|Odd|Even|) n =

    if i % 2 = 1 then Odd else Even

The Active Pattern can then be used in a match expression:

match 1 with

| Odd -> "Odd"

| Even -> "Even"

A partial Active Pattern goes one step further and tries to match a specified value returning an Option of either Some value if successful, or None otherwise.

The following FormulaText partial Active Pattern can use the same body as the parseFormula function we defined earlier:

let (|FormulaText|_|) (s:string) =

   if s.StartsWith "=" then Some(s.Substring(1))

   else None

As the following NumericValue can use the same body as the earlier parseNumber function:

let (|NumberValue|_|) (s:string) =

    match Decimal.TryParse(s) with

    | true, n -> Some(n)

    | false, _ –> None

Now the Active Patterns may be used to simplify the earlier parse function:

let parse s =

    match s with

    | FormulaText text -> Formula text

    | NumberValue n -> Number n

    | _ -> invalidOp "Unknown value type"

What Next?

Time to put your new F# and functional programming skills to work and try creating your own Spreadsheet via the tutorial on Developer Fusion:

• Functional Cells: A Spreadsheet in F#