An Introduction to Functional Languages: Part Two

Previously we gave an introduction to functional languages. Now we take a look at some functional programming examples with F#.

F# is a language which was developed in the Microsoft Research and has graduated to a general public release. It is considered to be OCaml on .Net, as it has strong ties to OCaml. What makes it significant to me is its tool support. As an addition to the .Net family of languages it has fantastic language support with Visual Studio. This is rarely the case with other functional languages and specifically the languages that interest me (Clojure, Scala, Erlang). F# is also a hybrid language. It has object-orient support and has the ability to be integrated into a C# or other CLR language with relative ease. Currently F# is strong typed language that uses type interference and runs on the CLR. I haven’t experienced it yet, but all signs indicate that it can be run on Mono.

/// A very simple constant integer
let int1 = 1
/// A function on integers
let f x = 2*x*x - 5*x + 3
// A simple tuple of integers
let pointA = (1, 2, 3)
// A simple tuple of an integer, a string and a floating point number
let dataB = (1, "fred", 3.1415)

Listing 1: F# let examples from Tutorials.fs

The first important operator in F# is let. When dealing with variables as in int1, it is important to realize that this is not really an imperative variable it is a symbolic assignment. let can also assign variables to functions as with the example of function f. The last two code examples are assignments of tuples. pointA is a sequence of all the same type while dataB is a sequence of multiple types. Listing 2 will show some lists and introduce some new operators in F#

Sequences in F#

let listA = [ ]  			/// The empty list
let listB = [ 1; 2; 3 ]  		/// A list with 3 integers
let listC = 1 :: [2; 3]  	/// A list with 3 integers, note :: is the 'cons' operation
let listD =  [5 .. 10]    	/// A list of number 15 through 10
let listE =  listC @ listD   	/// A concatenated list of listC and listD

/// Compute the sum of a list of integers using a recursive function
let rec SumList xs =
    match xs with
    | []    -> 0
    | h::t -> h + SumList t
/// Sum of a list
let sum = SumList [1; 2; 3]  

Listing 2: F# list examples 

The next important element of F# is working with lists. The list assignment code in listing 2 is easily readable with two exceptions, the :: and @ operators. The :: operator is the cons operator is another way of describing a list. It is great when used in pattern match, which we will see later. The @ operator concatenates two lists.

The function SumList is a recursive function (defined by the rec keyword). It takes a sequence; if the sequence is empty (defined by []) then 0 is returned, else the head of the sequence (h) is added to the recursive call of the SumList of the remaining sequence. It is very common in F# to see match for a sequence with head or h as the variable representing the head and tail or t representing the remainder of the sequence.

Working with a collection can be quite different using functional techniques. In Java for instance, the approach is to iterate over the collection, with perhaps a “for each” loop. In Groovy we would use an each method passing in a closure. In F# there is a List module and it is possible to pass a function of the List module a sequence. The function would be applied on each element of the sequence. Notice the abstraction from iterations and branching.

let Square x = x*x               /// A function that squares its input
let squares1 = List.map Square [1; 2; 3; 4]  // Map a function across a list of values

Listing 3: F# List map function 

The map function of the List module returns a new list (remember lists are immutable), with the same number of elements, each element being the square of the original list.

fun in F#

Another language feature of F# is the fun keyword. The fun keyword allows us to write an anonymous function on the fly. This would allow us to rewrite the functions from listing 3 as listing 4.

let squares2 = List.map (fun x -> x*x) [1; 2; 3; 4]

Listing 4: F# fun keyword defines a function on the fly

Of course this doesn’t allow for function reuse, but it can be a very convenient technique to simplify complex function creation.

Pipe operator in F#

For longer curried functions sometimes it is difficult to read what is happening or the order of execution. F# introduces an operator which makes this very easy, referred to as the pipe operator (|>). Listing 5 rewrites the functions from listing 3 and 4 one more time using the pipe operator.

let squares3 = [1; 2; 3; 4] |> List.map (fun x -> x*x) 

Listing 5: F# pipe operator

This time the sequence is piped into the List.map. In a currying way these pipe operators are often chained as in listing 6.

let SumOfSquaresUpTo n = 
  [1..n] 
  |> List.map Square 
  |> List.sum

Listing 6: F# pipe operator chaining

Discriminated Unions in F#

Another feature of F# is the ability to create a discriminated union, which is a type which is limited to a defined set of types. For instance:

type exampleUnion =
    | ex1 of int * string
    | ex2 of bool
    | ex3 
// constructing instances
let a = ex1(42,"life")
let b = ex3
let f du = 
    // pattern matching
    match du with
    | ex1(x,s) -> printfn "x is %d, s is %s" x s
    | ex2(b) -> printfn "b is %A" b
    | ex3 -> printfn "three"
 
f a  // x is 42, s is life
f b  // three

Listing 7: F# Discriminated Union

Listing 7 defines a type that is limited to an integer string pair, a boolean or nil. This can be incredibly useful when leverage with pattern matching as evident in this listing. This is a great example of a technique that can’t be done with a switch statement. Where a switch statement must be for a specific type, pattern matching in F# is capable of switching on the type and providing easy access to that types payload.

Since we are pattern matching, lets end with the Fibonacci sequence implementation if F#.

let rec fib n =
    match n with
    | 1      -> n
    | 2      -> 1
    | n      -> fib (n-1) + fib (n-2)

Listing 8: F# Fibonacci Function

This F# example is not as concise as the Mathematica example in listing 6, but close and very easy to read. Unlike Mathematica code however, F# is running on the CLR and is reasonably easy to integrate into a C# application.

Summary

This has been a whirlwind tour of the concept of functional programming. There are whole books written on the subject of functional programming and F# which don’t completely cover the subject. This article addresses some of the conceptual differences of functional development as faced by an individual who has worked solely with imperative languages. The concepts of lambda expressions, currying, closures and tuples were covered with sufficient detail to get started. F# examples were provided to put some of the defined terms to practice.

The need for functional programming is growing and the barrier to entry has never been smaller, its time to add functional programming to your knowledge portfolio. I would recommend taking a look at Scala or Clojure on the JVM or F# on the CLR.

Resources

Web

• http://en.wikipedia.org/wiki/Functional_programming 
• http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/default.aspx
• http://msdn.microsoft.com/en-us/fsharp/default.aspx 
• http://deepfriedbytes.com/podcast/episode-23-functional-programming-in-csharp-with-oliver-sturm/ 
• http://www.strangelights.com/fsharp/wiki/

Books

• Programming Scala by Venkat Subramaniam
• Programming Clojure by Stuart Halloway
• F# in a nutshell by Amanda Laucher and Ted Neward
• Expert F# by Don Syme
• Learning F# 1.0 by Chris Smith.
• Functional Programming in C# by Oliver Sturm