You are viewing a preview of this course. Sign in to start learning

Lesson 2: Functions, Pattern Matching, and Recursion

Master F# functions, explore powerful pattern matching capabilities, and understand recursive thinking in functional programming

Lesson 2: Functions, Pattern Matching, and Recursion

In this lesson, we'll dive deeper into F# by exploring three fundamental pillars of functional programming: functions as first-class values, pattern matching, and recursion. Building on the basics from Lesson 1, you'll learn how F# treats functions not just as code blocks, but as values that can be passed around, stored in variables, and combined in powerful ways. Functions in F# are first-class citizens, meaning they have the same status as any other value like integers or strings. This concept might seem strange if you're coming from imperative languages like C# or Java, but it's the key to unlocking functional programming's true potential. You can assign functions to variables, pass them as arguments to other functions (creating higher-order functions), and even return functions from other functions. This flexibility enables elegant solutions to complex problems and promotes code reuse in ways that traditional object-oriented programming cannot match.

Let's start with function syntax and function composition. In F#, you define functions using the let keyword, just like you would for values. The simplest form is: let functionName parameter = expression. Notice there are no parentheses or curly braces required - F# uses indentation and whitespace to define scope. Here's a concrete example:

let square x = x * x
let addTen x = x + 10
let squareThenAdd x = addTen (square x)

// Using it
let result = squareThenAdd 5  // First squares 5 (25), then adds 10 (35)

What makes this powerful is function composition, which allows you to combine simple functions into more complex ones. F# provides two operators for this: the forward pipe operator |> and the composition operator >>. The pipe operator takes a value and "pipes" it through a function, making code read more naturally from left to right:

let result = 5 |> square |> addTen  // Same as addTen(square(5))

// You can also compose functions themselves
let squareThenAddComposed = square >> addTen
let result2 = squareThenAddComposed 5  // Same result: 35

💡 Tip: The pipe operator |> is one of F#'s most beloved features. It transforms nested function calls like f(g(h(x))) into readable pipelines: x |> h |> g |> f. This reads naturally as "take x, apply h, then apply g, then apply f."

Pattern matching is arguably F#'s most powerful feature, going far beyond simple switch statements in other languages. It allows you to deconstruct data structures and make decisions based on the shape and content of your data simultaneously. The basic syntax uses the match keyword with a series of patterns followed by -> and the expression to evaluate. Each pattern is tried in order from top to bottom, and the first matching pattern wins. Here's a simple example matching on integers:

let describeNumber n =
    match n with
    | 0 -> "zero"
    | 1 -> "one"
    | 2 -> "two"
    | _ -> "many"  // The underscore _ is a wildcard that matches anything

let description = describeNumber 5  // Returns "many"

But pattern matching becomes truly powerful when working with tuples, lists, and discriminated unions (which we'll explore more in later lessons). You can match on structure and extract values in one step:

// Pattern matching with tuples
let describePoint point =
    match point with
    | (0, 0) -> "origin"
    | (x, 0) -> sprintf "on x-axis at %d" x
    | (0, y) -> sprintf "on y-axis at %d" y
    | (x, y) -> sprintf "at coordinates (%d, %d)" x y

// Pattern matching with lists
let describeList lst =
    match lst with
    | [] -> "empty list"
    | [x] -> sprintf "single element: %d" x
    | [x; y] -> sprintf "two elements: %d and %d" x y
    | head::tail -> sprintf "starts with %d, has %d more elements" head (List.length tail)

The list pattern head::tail uses the cons operator :: to split a list into its first element (head) and remaining elements (tail). This pattern is fundamental to recursive list processing in functional programming.

⚠️ Common Mistake: Pattern matching must be exhaustive - you must handle all possible cases. If the compiler can't prove you've covered everything, it will warn you. Always include a wildcard pattern _ or a variable pattern at the end if you haven't explicitly handled all cases.

Recursion is the functional programmer's alternative to loops. Instead of using for or while loops to iterate, functional languages prefer recursive functions - functions that call themselves with modified arguments until reaching a base case. This approach fits naturally with immutable data structures and pattern matching. Every recursive function needs two things: a base case that stops the recursion, and a recursive case that breaks the problem into smaller pieces. Let's look at a classic example - calculating factorial:

let rec factorial n =
    match n with
    | 0 -> 1                        // Base case
    | _ -> n * factorial (n - 1)    // Recursive case

let result = factorial 5  // 5 * 4 * 3 * 2 * 1 = 120

Notice the rec keyword after let - this tells F# that the function is recursive and allows it to call itself. Without rec, F# would report an error because the function name wouldn't be in scope within its own body. This explicit declaration helps prevent accidental recursion and makes the programmer's intent clear.

🔍 Deep Dive: F# and many functional languages support tail call optimization (TCO). When a recursive call is the very last operation in a function (a "tail call"), the compiler can optimize it into a loop, preventing stack overflow. The factorial example above is NOT tail-recursive because multiplication happens after the recursive call. Here's a tail-recursive version:

let factorial n =
    let rec factorialHelper n accumulator =
        match n with
        | 0 -> accumulator
        | _ -> factorialHelper (n - 1) (n * accumulator)
    factorialHelper n 1

let result = factorial 5  // Same result, but won't overflow on large inputs

The tail-recursive version uses an accumulator parameter to carry the result forward, ensuring the recursive call is the last operation. This pattern of using an inner helper function with an accumulator is extremely common in F# code.

Let's combine all three concepts - functions, pattern matching, and recursion - to process lists, one of the most common tasks in functional programming. Lists in F# are immutable linked lists, and the most natural way to process them is recursively. Here's a function that sums all elements in a list:

let rec sum lst =
    match lst with
    | [] -> 0                          // Base case: empty list sums to 0
    | head::tail -> head + sum tail    // Recursive case: add head to sum of tail

let total = sum [1; 2; 3; 4; 5]  // Returns 15

This pattern of matching on empty list and head::tail is so common it's worth memorizing. Let's look at more examples:

// Find length of a list
let rec length lst =
    match lst with
    | [] -> 0
    | _::tail -> 1 + length tail

// Find maximum element (assumes non-empty list)
let rec maximum lst =
    match lst with
    | [x] -> x
    | head::tail -> max head (maximum tail)
    | [] -> failwith "Cannot find maximum of empty list"

// Filter elements that satisfy a predicate
let rec filter predicate lst =
    match lst with
    | [] -> []
    | head::tail -> 
        if predicate head then
            head :: filter predicate tail
        else
            filter predicate tail

// Example: get only even numbers
let evens = filter (fun x -> x % 2 = 0) [1; 2; 3; 4; 5; 6]  // [2; 4; 6]

Notice the use of an anonymous function (also called a lambda) in the filter example: fun x -> x % 2 = 0. This creates a function inline without naming it. Anonymous functions are essential when working with higher-order functions.

🎯 Key Takeaway: The pattern of recursively processing lists by handling the empty case and the head::tail case is fundamental to functional programming. Once you internalize this pattern, you can solve countless list-processing problems elegantly.

Guards extend pattern matching by adding boolean conditions to patterns. You add a guard using the when keyword after a pattern. This lets you match based on both structure and logical conditions:

let categorizeNumber n =
    match n with
    | x when x < 0 -> "negative"
    | 0 -> "zero"
    | x when x < 10 -> "small positive"
    | x when x < 100 -> "medium positive"
    | _ -> "large positive"

let rec findFirst predicate lst =
    match lst with
    | [] -> None
    | head::tail when predicate head -> Some head
    | _::tail -> findFirst predicate tail

The second example introduces F#'s Option type (Some and None), which safely represents values that might not exist - we'll explore this more in the next lesson. Here, None indicates no element was found, while Some head wraps the found value.

Let's create a more complex example that combines everything we've learned. We'll build a simple calculator that evaluates expressions using recursive pattern matching:

// Define expression types
type Expression =
    | Number of int
    | Add of Expression * Expression
    | Multiply of Expression * Expression
    | Subtract of Expression * Expression

// Recursive evaluator
let rec evaluate expr =
    match expr with
    | Number n -> n
    | Add (left, right) -> evaluate left + evaluate right
    | Multiply (left, right) -> evaluate left * evaluate right
    | Subtract (left, right) -> evaluate left - evaluate right

// Build expression: (5 + 3) * 2
let expression = 
    Multiply(
        Add(Number 5, Number 3),
        Number 2
    )

let result = evaluate expression  // Returns 16

This example demonstrates discriminated unions, a powerful F# feature that lets you define types that can be one of several named cases. The evaluate function uses pattern matching to destructure each case and recursively evaluate sub-expressions.

📝 Try This: Extend the calculator to support division and handle division by zero safely. Add a new case Divide of Expression * Expression and use pattern matching with guards to check if the divisor evaluates to zero.

One more crucial concept: partial application and currying. In F#, all functions technically take only one argument. Multi-parameter functions are automatically curried, meaning they're transformed into a series of single-parameter functions. This enables partial application:

// This function appears to take two parameters
let add x y = x + y

// But it's actually equivalent to:
let add x = fun y -> x + y

// This means you can partially apply it:
let addFive = add 5  // Returns a function that adds 5 to its argument
let result = addFive 10  // Returns 15

// Partial application is incredibly useful with higher-order functions:
let numbers = [1; 2; 3; 4; 5]
let incremented = List.map (add 1) numbers  // [2; 3; 4; 5; 6]

The List.map function applies a function to every element in a list. By partially applying add, we create a function that adds 1, perfect for mapping. This technique eliminates the need for many temporary lambda functions and makes code more concise.

┌─────────────────────────────────────────────────────┐
│          RECURSION VISUALIZATION                    │
│                                                     │
│  factorial 3                                        │
│  │                                                  │
│  ├─→ 3 * factorial 2                               │
│  │   │                                              │
│  │   ├─→ 2 * factorial 1                           │
│  │   │   │                                          │
│  │   │   ├─→ 1 * factorial 0                       │
│  │   │   │   │                                      │
│  │   │   │   └─→ 1 (base case)                     │
│  │   │   │                                          │
│  │   │   └─→ 1 * 1 = 1                             │
│  │   │                                              │
│  │   └─→ 2 * 1 = 2                                 │
│  │                                                  │
│  └─→ 3 * 2 = 6                                     │
│                                                     │
└─────────────────────────────────────────────────────┘

In summary, functions, pattern matching, and recursion form the core toolkit of F# programming. Functions are values that can be composed and partially applied. Pattern matching lets you destructure data and make decisions elegantly in one step. Recursion replaces imperative loops with a declarative style that pairs naturally with immutable data structures. These concepts work together synergistically: you use pattern matching in recursive functions to process data structures, and you pass functions as arguments to create reusable, composable building blocks. Mastering these three concepts is essential before moving forward to more advanced functional programming techniques.

📚 Further Study

📝
Ready to practice?
This lesson has 19 questions to help you learn
Sign in to start learning

Sign in to access practice questions