Exercise 5: Pattern Matching and Recursion
Pattern matching in F# is similar to switch statements in C#; however they provide abilities and functionality beyond the C# construct, particularly when used in concert with F#’s implementation of lists and recursion. In this Exercise you will be introduced to F#’s pattern matching syntax and see some examples which highlight the power of pattern matching.
In this task you will learn the basic pattern matching syntax in F#.
The pattern matching syntax in F# is very straight forward. Enter the following code into the F# interactive console command prompt:
Whitespace is significant in the F# console. You’ll need to have at least one whitespace character to indent on subsequent lines after the first. The convention is to use four spaces, not a tab.
let patMatch x = match x with | 0 -> printfn "Value is 0" | 1 -> printfn "Value is 1" | _ -> printfn "Value is not 0 or 1";;
val patMatch : int -> unit
By stacking patterns with the | operator, it is possible to compare input values to various patterns. Enter the following code into the F# interactive command prompt:
let patMatch x = match x with | 0 | 1 -> printfn "Value is 0 or 1" | _ -> printfn "Value is not 0 or 1";;
val patMatch : int -> unit
F# also provides syntax to easily perform pattern matching over tuples. The next example will demonstrate how an if control structure for “anding” two values can be implemented with pattern matching. Enter the following code into the F# interactive command prompt:
let andTrue x = match x with | (true, true) -> true | _ -> false;;
val andTrue : bool * bool -> bool
This function takes a tuple made up of two boolean values and returns a boolean.
You can verify this code by calling it with the following tuples:
andTrue (false, true);;
val it : bool = false
andTrue (true, true);;
val it : bool = true
Task 2 – Using Simple Pattern Matching and Recursion to Implement the Fibonacci Sequence
In this task you will learn to supplement pattern matching in F# with recursive functions. Recursion is defining a function in terms of itself. In the following example if x is not 0 or 1, the function calls itself passing values derived from x. This approach is often used in functional programming in place of loops as it can make algorithms easier to understand.
To create a recursive function in F#, you must use the rec keyword. The example below is an F# implementation of a Fibonacci function which uses recursion to call itself to determine the result. Enter the following code into the F# interactive console command prompt:
let rec fib x = match x with | 0 -> 0 | 1 -> 1 | _ -> fib(x - 1) + fib(x - 2);;
val fib : int -> int
The
Fibonacci Sequence is a sequence of numbers where the next number in the sequence is defined by adding the value of the two numbers previous two it (starting with the first two number 0 and 1). For instance, here are the first 10 numbers in the Fibonacci Sequence starting with 0:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
Calling the function with the value of 42:
fib 42;;
val it : int = 267914296
The rec keyword is required in F# to indicate that a function is recursive.
Task 3 – Using Recursion with F# Lists
F#’s recursion ability also makes it ideal for processing items in a list. This task will simulate performing some sort of processing on items in a list in a recursive manner.
The function below takes a list as an argument. Here you leverage the power of pattern matching. Notice that pattern matching works with the :: operator you used earlier to build lists. So, if the list passed in is empty, you will simply print “done”. Otherwise, you are going to print the value of the head and then recursively call the function again to process the tail. Enter the following code into the F# interactive console command prompt:
let rec processList x = match x with | head::tail -> printfn "processing %i" head; processList tail | [] -> printfn "done";;
val processList : int list -> unit
In F# the single semi-colon can be used to separate different statements on the same line.
Also notice that F# was able to infer that the function accepts a list of integers merely because the string you printed used a formatting of “%i” (for int).
You will create a list to send to the function for processing. Enter the following code in the F# interactive console command prompt:
processList [1; 2; 3; 4; 5];;
processing 1 processing 2 processing 3 processing 4 processing 5 done val it : unit = ()
Next Step
Exercise 6: Types and Discriminated Unions