Higher-Order Functions

Higher-Order Functions in F#

Master higher-order functions in F# with free flashcards and spaced repetition practice. This lesson covers function composition, partial application, and common higher-order functions like map, filter, and fold—essential concepts for writing elegant, maintainable functional code.

Welcome to Higher-Order Functions 💻

Higher-order functions are one of the most powerful features in functional programming. A higher-order function is simply a function that either takes one or more functions as parameters, or returns a function as its result. This capability enables you to write concise, reusable code that separates what you want to do from how you want to do it.

In F#, functions are first-class values, meaning they can be passed around just like integers, strings, or any other data type. This opens up elegant patterns for data transformation, composition, and abstraction.

🤔 Did you know? The term "higher-order" comes from mathematical logic, where "first-order" functions operate on data, and "higher-order" functions operate on other functions!

Core Concepts

What Makes a Function Higher-Order? 🎯

A function qualifies as higher-order if it does at least one of the following:

1. Accepts functions as parameters
2. Returns a function as its result

Let's see both in action:

// Takes a function as a parameter
let applyTwice f x = f (f x)

let increment n = n + 1
let result = applyTwice increment 5  // Returns 7

// Returns a function
let makeAdder n = 
    fun x -> x + n

let addFive = makeAdder 5
let value = addFive 10  // Returns 15

The Big Three: Map, Filter, and Fold 🔺

These three higher-order functions form the foundation of list processing in functional programming:

💡 Tip: Think of these as assembly line operations: map transforms, filter selects, and fold combines.

List.map - Transforming Every Element 🎨

List.map applies a function to every element in a list, producing a new list of the same length:

let numbers = [1; 2; 3; 4; 5]

// Double every number
let doubled = List.map (fun x -> x * 2) numbers
// Result: [2; 4; 6; 8; 10]

// Convert to strings
let strings = List.map string numbers
// Result: ["1"; "2"; "3"; "4"; "5"]

// Use with named functions
let square x = x * x
let squared = List.map square numbers
// Result: [1; 4; 9; 16; 25]

Key insight: map preserves the structure (length and order) while transforming the content.

VISUAL: List.map Process

Input:     [1,  2,  3,  4,  5]
            ↓   ↓   ↓   ↓   ↓
Function:  (x -> x * 2)
            ↓   ↓   ↓   ↓   ↓
Output:    [2,  4,  6,  8, 10]

Same length, transformed values

List.filter - Selecting Elements 🔍

List.filter keeps only elements that satisfy a predicate (a function returning bool):

let numbers = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

// Keep only even numbers
let evens = List.filter (fun x -> x % 2 = 0) numbers
// Result: [2; 4; 6; 8; 10]

// Keep numbers greater than 5
let large = List.filter (fun x -> x > 5) numbers
// Result: [6; 7; 8; 9; 10]

// Filter with named predicates
let isPositive x = x > 0
let positives = List.filter isPositive [-2; -1; 0; 1; 2]
// Result: [1; 2]

Key insight: filter changes the length but keeps the type and order of surviving elements.

VISUAL: List.filter Process

Input:      [1,  2,  3,  4,  5,  6]
             ↓   ↓   ↓   ↓   ↓   ↓
Predicate:  (x % 2 = 0)?
            ❌  ✅  ❌  ✅  ❌  ✅
             ↓       ↓       ↓
Output:     [2,      4,      6]

Fewer elements, same type

List.fold - Accumulating Results 🌀

List.fold (also called reduce in some languages) processes each element while maintaining an accumulator:

let numbers = [1; 2; 3; 4; 5]

// Sum all numbers
let sum = List.fold (fun acc x -> acc + x) 0 numbers
// Result: 15

// Find maximum
let max = List.fold (fun acc x -> if x > acc then x else acc) numbers.[0] numbers
// Result: 5

// Build a string
let concatenated = List.fold (fun acc x -> acc + string x) "" numbers
// Result: "12345"

Signature breakdown: List.fold (folder: 's -> 'a -> 's) (initial: 's) (list: 'a list) : 's

• folder: function taking (accumulator, element) → new accumulator
• initial: starting value for the accumulator
• list: the list to process
• Returns: final accumulator value

VISUAL: List.fold Process (sum example)

Initial:  acc = 0
          ↓
Step 1:   acc + 1 = 1
          ↓
Step 2:   acc + 2 = 3
          ↓
Step 3:   acc + 3 = 6
          ↓
Step 4:   acc + 4 = 10
          ↓
Step 5:   acc + 5 = 15 (final)

List: [1, 2, 3, 4, 5] → Result: 15

🧠 Mnemonic: "Fold" = "fold ingredients into a mixture" - you're combining each item into an accumulated result.

Function Composition 🔗

Function composition combines multiple functions into a new function. F# provides two operators:

• >> (forward composition): f >> g means "apply f, then g"
• << (backward composition): f << g means "apply g, then f"

// Individual functions
let addOne x = x + 1
let double x = x * 2
let square x = x * x

// Forward composition (reads left to right)
let addOneThenDouble = addOne >> double
let result1 = addOneThenDouble 5  // (5 + 1) * 2 = 12

// Backward composition (reads right to left)
let doubleAfterAddOne = double << addOne
let result2 = doubleAfterAddOne 5  // (5 + 1) * 2 = 12

// Chain multiple functions
let pipeline = addOne >> double >> square
let result3 = pipeline 2  // ((2 + 1) * 2)^2 = 36

💡 Tip: Use >> for natural left-to-right reading. It matches the pipeline operator |> style.

COMPOSITION FLOW

Forward (>>):  f >> g >> h
               ┌───┐   ┌───┐   ┌───┐
    Input ──→  │ f │──→│ g │──→│ h │──→ Output
               └───┘   └───┘   └───┘

Backward (<<): f << g << h  
               ┌───┐   ┌───┐   ┌───┐
    Input ──→  │ h │──→│ g │──→│ f │──→ Output
               └───┘   └───┘   └───┘
               (applied right to left)

Partial Application ⚡

Partial application means calling a multi-parameter function with fewer arguments than it expects, which returns a new function waiting for the remaining arguments:

// Function with two parameters
let add x y = x + y

// Partially apply the first parameter
let addFive = add 5
// addFive is now: fun y -> 5 + y

let result = addFive 3  // Returns 8

// Practical example: specialized filters
let greaterThan threshold x = x > threshold

let isAdult = greaterThan 18
let isSenior = greaterThan 65

let ages = [15; 25; 45; 70]
let adults = List.filter isAdult ages    // [25; 45; 70]
let seniors = List.filter isSenior ages  // [70]

🌍 Real-world analogy: Partial application is like a coffee shop where you order "large coffee" first, then later specify "with milk" or "black". Each step narrows down the final product.

Piping and Data Flow 🚰

The pipe operator |> feeds a value into a function, enabling readable left-to-right data transformations:

let numbers = [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

// Without piping (nested, hard to read)
let result1 = 
    List.sum (List.map (fun x -> x * x) (List.filter (fun x -> x % 2 = 0) numbers))

// With piping (clear, sequential)
let result2 = 
    numbers
    |> List.filter (fun x -> x % 2 = 0)  // Keep evens: [2; 4; 6; 8; 10]
    |> List.map (fun x -> x * x)          // Square: [4; 16; 36; 64; 100]
    |> List.sum                            // Sum: 220

// Both result1 and result2 equal 220

💡 Tip: Piping transforms imperative loops into declarative transformations. Think "data flow" not "control flow."

PIPELINE VISUALIZATION

[1;2;3;4;5;6;7;8;9;10]
         │
         ↓ (filter evens)
    [2;4;6;8;10]
         │
         ↓ (map square)
  [4;16;36;64;100]
         │
         ↓ (sum)
        220

Each stage transforms the data

Example 1: Processing Student Records 📚

Let's combine multiple higher-order functions to process student data:

type Student = {
    Name: string
    Grade: int
    Age: int
}

let students = [
    { Name = "Alice"; Grade = 85; Age = 20 }
    { Name = "Bob"; Grade = 72; Age = 19 }
    { Name = "Charlie"; Grade = 91; Age = 21 }
    { Name = "Diana"; Grade = 78; Age = 20 }
    { Name = "Eve"; Grade = 95; Age = 22 }
]

// Find average grade of students who passed (grade >= 75)
let averagePassingGrade = 
    students
    |> List.filter (fun s -> s.Grade >= 75)     // Keep passing students
    |> List.map (fun s -> s.Grade)               // Extract grades
    |> List.average                               // Calculate average
    |> int                                        // Convert to int
// Result: 87

// Get names of top performers (grade >= 90), sorted
let topPerformers = 
    students
    |> List.filter (fun s -> s.Grade >= 90)
    |> List.sortByDescending (fun s -> s.Grade)
    |> List.map (fun s -> s.Name)
// Result: ["Eve"; "Charlie"]

Key lessons:

• Each step handles one responsibility
• The code reads like natural language
• Easy to modify (add/remove steps)
• Type-safe at every stage

Example 2: Custom Higher-Order Functions 🛠️

Create your own higher-order functions for specialized tasks:

// Apply a function n times
let rec applyN times f x =
    if times <= 0 then x
    else applyN (times - 1) f (f x)

let increment x = x + 1
let result = applyN 5 increment 10  // Apply increment 5 times: 15

// Compose a list of functions
let composeAll functions =
    List.fold (>>) id functions  // id is the identity function (fun x -> x)

let pipeline = composeAll [addOne; double; square]
let value = pipeline 2  // ((2 + 1) * 2)^2 = 36

// Conditional application
let applyIf condition f x =
    if condition x then f x else x

let doubleIfEven = applyIf (fun x -> x % 2 = 0) (fun x -> x * 2)
let a = doubleIfEven 4  // 8 (even, so doubled)
let b = doubleIfEven 5  // 5 (odd, unchanged)

Example 3: Real-World Data Pipeline 🌍

Process web API data using higher-order functions:

type Product = {
    Id: int
    Name: string
    Price: decimal
    Category: string
    InStock: bool
}

let products = [
    { Id = 1; Name = "Laptop"; Price = 999.99m; Category = "Electronics"; InStock = true }
    { Id = 2; Name = "Mouse"; Price = 25.50m; Category = "Electronics"; InStock = true }
    { Id = 3; Name = "Desk"; Price = 350.00m; Category = "Furniture"; InStock = false }
    { Id = 4; Name = "Chair"; Price = 150.00m; Category = "Furniture"; InStock = true }
    { Id = 5; Name = "Monitor"; Price = 300.00m; Category = "Electronics"; InStock = true }
]

// Business logic: Apply 10% discount to in-stock electronics
let discountedElectronics = 
    products
    |> List.filter (fun p -> p.Category = "Electronics" && p.InStock)
    |> List.map (fun p -> { p with Price = p.Price * 0.9m })
    |> List.sortBy (fun p -> p.Price)

// Calculate total inventory value by category
let inventoryValue = 
    products
    |> List.filter (fun p -> p.InStock)
    |> List.groupBy (fun p -> p.Category)
    |> List.map (fun (category, items) -> 
        category, List.sumBy (fun p -> p.Price) items)
// Result: [("Electronics", 1325.49); ("Furniture", 150.00)]

Example 4: Function Factories 🏭

Higher-order functions can generate specialized functions:

// Create validators
let makeRangeValidator min max = 
    fun value -> value >= min && value <= max

let isValidAge = makeRangeValidator 0 120
let isValidPercentage = makeRangeValidator 0 100

let age1 = isValidAge 25      // true
let age2 = isValidAge 150     // false
let percent1 = isValidPercentage 85  // true

// Create formatters
let makeFormatter prefix suffix = 
    fun value -> sprintf "%s%s%s" prefix value suffix

let formatPrice = makeFormatter "$" ""
let formatPercentage = makeFormatter "" "%"

let price = formatPrice "19.99"      // "$19.99"
let discount = formatPercentage "20" // "20%"

// Retry logic (higher-order function for resilience)
let rec retry times f = 
    try
        f()
    with
    | ex when times > 1 -> 
        printfn "Retry: %s" ex.Message
        retry (times - 1) f
    | ex -> 
        raise ex

// Usage:
// retry 3 (fun () -> riskyOperation())

Common Mistakes ⚠️

Mistake 1: Confusing map and iter

// ❌ WRONG: Using map for side effects
let numbers = [1; 2; 3]
List.map (fun x -> printfn "%d" x) numbers  // Returns [(); (); ()], wasteful

// ✅ RIGHT: Use iter for side effects
List.iter (fun x -> printfn "%d" x) numbers  // Returns unit, clear intent

Key: map transforms and returns values. iter performs actions and returns nothing.

Mistake 2: Wrong fold direction

let items = ["Hello"; " "; "World"]

// ❌ WRONG: Using fold when order matters for non-associative operations
let result1 = List.fold (fun acc x -> x + acc) "" items
// Result: "World Hello" (backward!)

// ✅ RIGHT: Use fold with correct parameter order
let result2 = List.fold (fun acc x -> acc + x) "" items
// Result: "Hello World"

// OR use foldBack if you need right-to-left
let result3 = List.foldBack (fun x acc -> x + acc) items ""
// Result: "Hello World"

Mistake 3: Overusing anonymous functions

// ❌ HARD TO READ: Nested anonymous functions
let result = 
    numbers
    |> List.filter (fun x -> x % 2 = 0)
    |> List.map (fun x -> x * x)
    |> List.filter (fun x -> x > 10)
    |> List.map (fun x -> string x)

// ✅ BETTER: Extract named functions for clarity
let isEven x = x % 2 = 0
let square x = x * x
let isLarge x = x > 10

let result = 
    numbers
    |> List.filter isEven
    |> List.map square
    |> List.filter isLarge
    |> List.map string

💡 Tip: If a lambda is used more than once or is complex, give it a name!

Mistake 4: Forgetting partial application order

// ❌ WRONG: Parameters in wrong order for partial application
let divide x y = x / y
let divideBy2 = divide 2  // Creates (2 / y), not (x / 2)!

// ✅ RIGHT: Put the varying parameter last
let divide y x = x / y
let divideBy2 = divide 2  // Creates (x / 2) ✓

// OR use explicit lambda
let divideBy2 = fun x -> x / 2

Mistake 5: Ignoring performance with chains

// ❌ INEFFICIENT: Multiple passes through the list
let result = 
    largeList
    |> List.map expensiveFunction1
    |> List.map expensiveFunction2
    |> List.map expensiveFunction3

// ✅ BETTER: Compose functions, single pass
let combinedFunction = expensiveFunction1 >> expensiveFunction2 >> expensiveFunction3
let result = List.map combinedFunction largeList

// ✅ OR: Combine operations in one lambda
let result = 
    largeList
    |> List.map (fun x -> 
        x |> expensiveFunction1 |> expensiveFunction2 |> expensiveFunction3)

Key Takeaways 🎯

1. Higher-order functions accept functions as parameters or return functions as results
2. map transforms each element (preserves length)
3. filter selects elements matching a predicate (changes length)
4. fold accumulates elements into a single result (reduces to one value)
5. Composition (>> and <<) combines functions into pipelines
6. Partial application creates specialized functions from general ones
7. Piping (|>) makes data transformations readable left-to-right
8. Use iter for side effects, not map
9. Extract named functions when lambdas get complex
10. Compose functions to minimize passes through collections

🔧 Try this: Take an existing imperative loop in your code and rewrite it using map, filter, or fold. Notice how the intent becomes clearer!

📚 Further Study

1. F# for Fun and Profit - Higher Order Functions: https://fsharpforfunandprofit.com/posts/elevated-world/
2. Microsoft F# Language Reference - Functions: https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/functions/
3. F# Collections Documentation: https://fsharp.github.io/fsharp-core-docs/reference/fsharp-collections.html