Get started with functional programming and F#

We all learned about mathematical functions when we studied algebra: y = f(x), where f(x) = ax²+…. In the abstract world of mathematics, functions are pure and reproducible and have no side effects.

In imperative programming languages such as C, functions (in the sense of subroutines that return a value) are often anything but pure, since they rely on internal and external state, and they may change their behavior from one invocation to another. While it's often useful and expedient to have functions with side effects, they can be complicated to debug and may present a nightmare for a maintainer.

A branch of mathematics called lambda calculus (λ-calculus), which originated with the work of Alonzo Church in the 1930s, underlies the idea of functional programming. Among the formal aspects of λ-calculus that apply to functional programming are anonymous functions, also called lambda functions; currying, which transforms a multivariate function into a chain of univariate functions, thus allowing them to conform to the λ-calculus rule that functions may only have a single input; and functions as first-class values, meaning that functions can be the inputs and outputs of other functions.

In the following article, I give you an overview of functional programming and walk you through examples in F# to help you make the switch.

What is functional programming?

Functional programming languages must have first-class functions, meaning that the language treats functions as first-class values, which we defined as allowing functions to be the inputs and outputs of other functions. Higher-order functions are functions that take other functions as arguments.

In general, functional languages prefer recursion, mapping, and folding to iteration; purely functional languages such as Haskell lack loop constructs entirely. In addition, functional languages prefer pure functions to functions with side effects, although in real life there have to be exceptions to allow for file input and output.

On the other hand, functions in functional languages may use nonlocal variables. Returning the results of a function that uses nonlocal variables creates a closure. Closures usually require support for garbage collection in the language, so the memory used by the closure can be recovered when it goes out of scope.

Functional programming languages may have lambda (anonymous) functions. These can make the language more concise and make it easier to express nested functions, which are functions defined inside the scope of another function. Some theorists don't consider a language to be functional unless it has lambdas, nested functions, and closures in addition to first-class and higher-order functions.

The value of a variable in a functional program is supposed to be immutable, meaning it never changes once defined. That eliminates side effects and makes functional programs referentially transparent.

Composition of first-class functions into higher-order functions is a powerful way of reusing code. This coding style usually winds up being both concise and comprehensible.

What languages support functional programming?

Scheme, ML, Haskell, Clojure, F#, Common Lisp, and Scala (in no particular order) are all functional languages and support higher-order functions, lambda functions, and closures. Haskell in particular was designed to be an open standard for functional programming research.

Many other languages support some or all of these features while being classified in other groups. For example, JavaScript, Lua, and Perl 6 are scripting languages that support functional programming; C++ 11, C# 3+, and Rust are C-like languages that support functional programming; and MATLAB, Smalltalk, and Swift have functional programming support while having different primary emphases (numerical computing, object-oriented programming, and general purpose, respectively).

For the purposes of this tutorial, we’ll focus on examples of functional programming using F#.

About F#

F# is a strongly typed, functional-first programming language that was based on ML and built on top of the .Net Framework by Don Syme at Microsoft Research in Cambridge, England. It's not a pure functional language, since it also supports other programming paradigms, but you can use it to write in the functional style without having to add any packages or libraries. You can also use it in other styles, such as object-oriented and imperative programming. As a very pragmatic programmer, I consider that a plus, although functional programming partisans might disagree.

The current version of F# is free, open source, and cross-platform, and it's developed under the auspices of the F# Software Foundation. It runs on Linux, MacOS, Android, iOS, Windows, GPUs, and browsers.

Use F#

Before we dive into actual functional programming in F#, you should either have F# and an editor installed, and/or have the Try F# page running in your browser. The latter is less work, but requires Silverlight; on my Mac, it no longer works in Chrome or Safari, but does work in Firefox. In a pinch, you can use .Net Fiddle, set to the F# language, which doesn't seem to require any plugins.

How you install an F# compiler, and what IDE and other tools you can use, depends on your system. On a Mac you can install Xamarin Studio, Mono, the Visual Studio for Mac preview, Visual Studio Code and Ionide-fsharp, follow the Homebrew recipe for Mono, and/or build from source.

On Linux you can use apt-get (Debian), yum (RedHat), or emerge (GenToo) to install mono-complete and f-sharp, then install Visual Studio Code and Ionide-fsharp. On Windows, install Visual Studio and when you create an F# project you'll have the opportunity to install the Visual F# tools; if you prefer a lightweight editor, install Visual Studio Code and Ionide-fsharp.

Basic F#

Let's start with basic F#. If you are already comfortable with F#, feel free to skip down to the next section. These snippets are based on the F# cheatsheet, Try F#, F# for Fun and Profit, F# Snippits, and the F# documentation. You should try each snippet yourself.

Comments

(* This is a block comment *)
// And this is a line comment

Definition and assignments

Note that the types in the definitions below are inferred, but strong. That means you don't have to state the types explicitly, but can't change them after the definition.

Variables defined with let are immutable by default, which is consistent with functional programming principles.

let result = 1 + 1

However, you can explicitly make a variable mutable.

let mutable modifiable = "original value"

Assignment uses a different operator (<-) than definition and equality (=).

modifiable <- "new value"

Functions

In the definition below, square is a function -- no parentheses are needed.

let square x = x * x

Invoke the function -- no parentheses are needed here, either.

square 2

To define a lambda (anonymous) function or expression, use the fun keyword and the production operator ->.

let squareIt = fun n -> n * n

Factorial is a recursive function, enabled by the rec keyword.

let rec factorial x =
   if x < 1 then 1
   else x * factorial (x - 1)

Fibonacci is recursive and uses pattern matching via the match keyword and the case operator |. This function only uses constant patterns and the wildcard pattern _, but patterns are much more generalized.

let rec fibonacci n =
   match n with
       | 0 -> 0
       | 1 -> 1
       | _ -> fibonacci (n - 1) + fibonacci (n - 2)

You can also do pattern matching with the function keyword. See the F# Pattern Matching reference on MSDN for more detail.

You might think that recursive functions would of necessity be inefficient and tend to blow up the stack. That might have been true a decade or two ago, but today tail recursion can be optimized by the compiler to generate essentially the same code as you'd get from an iterative solution, assuming you write your recursive function to conform to the tail recursion pattern, typically by using an accumulator variable.

Examples of functional programming in F#

There are a number of ways of combining functions in F# to make higher-order functions. You can define composite functions with parentheses, the pipe operator, and the composition operator.

If we take these definitions for the functions being combined:

let negate x = x * -1
let square x = x * x
let print x = printfn "The number is: %d" x

… then the following three composite function definitions are equivalent.

Using parentheses:

let squareNegateThenPrint1 x =
   print (negate (square x))

Using the pipe operator |>:

let squareNegateThenPrint2 x =
   x |> square |> negate |> print

Using the composition operator >>:

let squareNegateThenPrint3 =
   square >> negate >> print

Lists, tuples, arrays, and sequences

Functions and variables alone do not a functional language make. At some point, you need data structures.

Lists, denoted by square brackets, with elements separated by semicolons or newlines, require all elements to be of the same type. Functions held in a list must all have the same signature. Lists are ordered and immutable.

List declarations can also be done with ranges and sequence expressions. Two colons, the cons operator ::, are used in pattern matching (as shown in quicksort2 below) to separate the head from the tail of a list.

let integerList = [ 1; 2; 3; 4; 5; 6; 7 ] 
let stringList = [ "one"; "two"; "three" ] 
let funList = [ negate; square ] //functions
let list1 = [ 1 .. 10 ] //range
let listOfSquares = [ for i in 1 .. 10 -> i*i ]//sequence expression

//A Quicksort implementation using lists 
letrecquicksort2 = function
    | [] -> []                    
    | first::rest ->
        let smaller,larger = List.partition ((>=) first) rest
        List.concat [quicksort2 smaller; [first]; quicksort2 larger]

// test code       
printfn "%A" (quicksort2 [1;5;23;18;9;1;3])

Tuples, denoted by parentheses, do not require their elements to be of the same type. Function elements in tuples do not all need to have the same signature.

let integerTuple = ( 1, -7 ) 
let stringTuple = ( "one", "two", "three" ) 
let mixedTuple = ( 1, "two", 3.3 )
let moreMixedTuple = ( result,"two",3.3, square, result+1 )

Arrays, denoted by [| and |] with elements separated by semicolons or newlines, are zero-based mutable collections of data elements of the same type. You can also use ranges and sequence expressions to create arrays.

let array1 = [| 1; 2; 3 |] 
let array2 = [| 1 .. 10 |] 
let array3 = [| for i in 1 .. 10 -> i * i |]

Arrays can have more than one dimension. Array slicing can return rows or columns from multidimensional arrays. The Array library module supports operations on one-dimensional arrays; Array2D, Array3D, and Array4D support two-, three-, and four-dimensional arrays. System.Array can also create arrays of rank greater than four. These are all discussed in the Microsoft F# documentation.

Sequences

A sequence, denoted by the seq keyword, curly brackets { }, and often the range operator .. (double period) is a logical series of elements all of one type. Sequence expressions are expressions that evaluate to a sequence. Two sets of double periods are used to specify a sequence with an increment. Sequence expressions can use the yield or production -> operators to add values to a sequence. Sequences use lazy evaluation of their elements. An if statement in a sequence acts as a filter.

seq { 1 .. 5 } //1,2,3,4,5 
seq { 0 .. 10 .. 100 } //0,10,20,…100 
seq { for i in 1 .. 10 do yield i * i } 
seq { for i in 1 .. 10 -> i * i }

let isprime n =
      let rec check i =
          i > n/2 || (n % i <> 0 && check (i + 1))
      check 2 

let aSequence = seq { for n in 1..100 do if isprime n then yield n } 
for x in aSequence do
      printfn "%d" x

Curried functions

Currying (named after Haskell B. Curry, the 20th-century combinatory logician) is a process that transforms a function that has more than one parameter into a series of embedded functions, each of which has a single parameter. In F#, functions of more than one parameter are implicitly curried unless parameters are tuples.

Currying allows for the partial application of function parameters. The idea of partial application is that if you fix the first N parameters of the function, you get a function of the remaining parameters. That can help when you are applying functions to a list or composing functions.

Parameters as tuples are used to inhibit currying when calling .Net Framework methods, for consistency with C#.

let compose4 op1 op2 n = op1 (op2 n)

//The function above implicitly generates code like the below
let compose4curried =
      fun op1 ->
          fun op2 ->
              fun n -> op1 (op2 n)