Lambdas, closures and higher-order functions

fun x -> x * 2 is a complete function with no name and no return, and F# lets you store it in a list, pass it to List.map or return it from another function. Below, a Map of four pricing functions handles four tickets, and not one line of the pricing code names a rule.

You will write lambdas, pass and return functions, build that dispatch tabledispatch table: A lookup table from keys to functions, such as a Map from a rule's name to the function that applies it, used instead of a long match: adding a case means adding an entry., see exactly what a closure keeps, including the one case where three closures share a value, and replace the reference cell operators that F# 6 deprecated. Five sessions recorded on .NET 10 back every rule.

A lambda is a function without a name

A lambda expressionlambda expression: An unnamed function written with fun, its parameters, an arrow and a body, such as fun x -> x * 2. It is a value: it can be passed, returned, stored in a list or bound to a name with let. is written fun, its parameters, an arrow and a body. Here are lambdas bound to a name, passed straight to library functions, and kept in a list:

from session import fsi

# Lambdas bound to a name, passed straight to List.map and List.filter, and kept in a list like any other value.
fsi([
    "let double = fun x -> x * 2;;",
    "[ 1; 2; 3 ] |> List.map double;;",
    "[ 1; 2; 3 ] |> List.map (fun x -> x * x);;",
    'let adults = [ "Asha", 34; "Kiran", 15 ] |> List.filter (fun (_, age) -> age >= 18);;',
    "let steps = [ double; (fun x -> x + 1); (fun x -> x - 3) ];;",
    "steps |> List.map (fun f -> f 100);;",
    "#quit;;",
], args=["--nologo"])

$ dotnet fsi --nologo
> let double = fun x -> x * 2;;
val double: x: int -> int

> [ 1; 2; 3 ] |> List.map double;;
val it: int list = [2; 4; 6]

> [ 1; 2; 3 ] |> List.map (fun x -> x * x);;
val it: int list = [1; 4; 9]

> let adults = [ "Asha", 34; "Kiran", 15 ] |> List.filter (fun (_, age) -> age >= 18);;
val adults: (string * int) list = [("Asha", 34)]

> let steps = [ double; (fun x -> x + 1); (fun x -> x - 3) ];;
val steps: (int -> int) list =
  [<fun:steps@5>; <fun:steps@5-1>; <fun:steps@5-2>]

> steps |> List.map (fun f -> f 100);;
val it: int list = [200; 101; 97]

> #quit;;

let double = fun x -> x * 2 printed the same signature that let double x = x * 2 would, x: int -> int: the two forms define the same function. Passed to List.map, a lambda saves you from naming a function you need once, which is the use the Lambda Expressions reference gives for them. The parameter list can be any pattern, so fun (_, age) -> age >= 18 takes a tuple apart and ignores its first item.

The last two entries show that a function is a value like any other. steps holds double and two lambdas, all of type int -> int, and F# Interactive printed them as <fun:…> because a function has no printed form. Step through what List.map did with them:

In fun f -> f 100, the parameter f is itself a function. Nothing about List.map changes: it calls the lambda on each item, whatever the items are.

Functions go in, and functions come out

A higher-order functionhigher-order function: A function that takes another function as an argument, returns one as its result, or both, such as List.map, which takes the function to apply to each item. takes a function as an argument, returns one as its result, or both. The Using functions tutorial lists both among what makes functions first-class values in F#:

from session import fsi, run

# A function that takes a function, a function that returns one, then fares.fsx, a Map of functions.
fsi([
    "let applyTwice f x = f (f x);;",
    "applyTwice (fun x -> x * 2) 5;;",
    "let makeDiscount percent = fun price -> price - price * percent / 100;;",
    "let tenOff = makeDiscount 10;;",
    "tenOff 500;;",
    "applyTwice tenOff 500;;",
    "#quit;;",
], args=["--nologo"])
run("""
dotnet fsi fares.fsx
""")

$ dotnet fsi --nologo
> let applyTwice f x = f (f x);;
val applyTwice: f: ('a -> 'a) -> x: 'a -> 'a

> applyTwice (fun x -> x * 2) 5;;
val it: int = 20

> let makeDiscount percent = fun price -> price - price * percent / 100;;
val makeDiscount: percent: int -> price: int -> int

> let tenOff = makeDiscount 10;;
val tenOff: (int -> int)

> tenOff 500;;
val it: int = 450

> applyTwice tenOff 500;;
val it: int = 405

> #quit;;
$ dotnet fsi fares.fsx
Asha  senior    480.00
Ravi  student   600.00
Meera child     400.00
Dev   pilgrim  refused: no rule called pilgrim

applyTwice f x = f (f x) takes a function f and calls it twice, so its signature starts with f: ('a -> 'a): a function from a type to the same type, because the result goes back in. makeDiscount 10 returns a function, which F# Interactive printed as val tenOff: (int -> int), and applyTwice tenOff 500 took 10 % off twice: 500, then 450, then 405. The FSharp.Core collection functions follow the same order: List.map f xs takes the function first and the list last, so they partially apply and pipe well.

Functions as values also replace a common C# shape, a switch over names. fares.fsx keeps its rules in a Map from a rule’s name to the function that prices it, and price looks the rule up with Map.tryFind:

type Ticket = { Passenger: string; Rule: string; Fare: decimal }

// A dispatch table: each rule's name maps to the function that prices it.
let rules: Map<string, decimal -> decimal> =
    Map [ "standard", id
          "senior", fun fare -> fare * 0.6m
          "student", fun fare -> fare * 0.75m
          "child", fun fare -> fare / 2m ]

let price ticket =
    match Map.tryFind ticket.Rule rules with
    | Some rule -> Ok(rule ticket.Fare)
    | None -> Error $"no rule called {ticket.Rule}"

let tickets =
    [ { Passenger = "Asha"; Rule = "senior"; Fare = 800m }
      { Passenger = "Ravi"; Rule = "student"; Fare = 800m }
      { Passenger = "Meera"; Rule = "child"; Fare = 800m }
      { Passenger = "Dev"; Rule = "pilgrim"; Fare = 800m } ]

for t in tickets do
    match price t with
    | Ok fare -> printfn "%-5s %-8s %7.2f" t.Passenger t.Rule fare
    | Error message -> printfn "%-5s %-8s refused: %s" t.Passenger t.Rule message

Asha’s senior fare of 800 became 480.00 and Ravi’s student fare 600.00, through the same two lines of price. Dev’s pilgrim rule is not a key of the Map, so Map.tryFind returned None and price returned an Error instead of throwing. Adding a rule means adding one entry; price does not change.

A closure keeps what it captured

A lambda can use values from the place where it was created. The function together with those values is a closureclosure: A function value together with the values it uses from the scope where it was created. A captured immutable value stays as it was; a captured let mutable local is shared through a reference cell.. Two programs show what a closure keeps, first with counters, then with closures made in loops:

// Each call of makeCounter makes a new count, and the function it returns keeps that count.
let makeCounter () =
    let mutable count = 0

    fun () ->
        count <- count + 1
        count

let a = makeCounter ()
let b = makeCounter ()

printfn "a: %d, a: %d, b: %d, a: %d" (a ()) (a ()) (b ()) (a ())

// Three closures from a for loop: each pass binds a new i, and each closure keeps its own.
let fromFor = [ for i in 1..3 -> fun () -> i ]

// Three closures from a while loop over one let mutable: all three share it.
let fromWhile =
    let mutable i = 0
    let made = ResizeArray()

    while i < 3 do
        i <- i + 1
        made.Add(fun () -> i)

    List.ofSeq made

// The fix: copy the current value into a new immutable name before capturing it.
let fromWhileFixed =
    let mutable i = 0
    let made = ResizeArray()

    while i < 3 do
        i <- i + 1
        let current = i
        made.Add(fun () -> current)

    List.ofSeq made

printfn "for loop:        %A" (fromFor |> List.map (fun f -> f ()))
printfn "while, shared i: %A" (fromWhile |> List.map (fun f -> f ()))
printfn "while, copied:   %A" (fromWhileFixed |> List.map (fun f -> f ()))

from session import run

# Two counters, then closures made in a for loop and in a while loop, with and without warning 3180.
run("""
dotnet fsi counters.fsx
dotnet fsi capture.fsx
dotnet fsi --warnon:3180 capture.fsx
""")

$ dotnet fsi counters.fsx
a: 1, a: 2, b: 1, a: 3
$ dotnet fsi capture.fsx
for loop:        [1; 2; 3]
while, shared i: [3; 3; 3]
while, copied:   [1; 2; 3]
$ dotnet fsi --warnon:3180 capture.fsx


capture.fsx(6,17): warning FS3180: The mutable local 'i' is implicitly allocated as a reference cell because it has been captured by a closure. This warning is for informational purposes only to indicate where implicit allocations are performed.

for loop:        [1; 2; 3]
while, shared i: [3; 3; 3]
while, copied:   [1; 2; 3]

Each call of makeCounter creates a new count, so a and b count separately: a printed 1, 2 and 3, and b printed 1 in between. count is a let mutable local that must outlive the call that created it, and the Values reference explains how: a mutable value captured by a closure may be promoted to a reference cellreference cell: A small heap object that holds one value that can be changed, created with ref and read or written through .Value. The compiler creates one when a closure captures a let mutable local. More in “Values, expressions and immutability”, and warning 3180, off by default, reports where. The values lesson of this track stepped through one such counter; the loops of capture.fsx show what the cell means when several closures capture the same variable:

The for loop binds a new i in every pass, so its three closures kept 1, 2 and 3. The while loop has one mutable i, now one cell, and its three closures all read that cell after the loop had set it to 3: [3; 3; 3]. --warnon:3180 pointed at line 6, the declaration of that i, and at no line of the fixed loop, whose closures capture current, an immutable copy made in each pass.

Sharing is not always a bug: makeCounter depends on it. It becomes one when each closure was meant to keep a value of its own.

Write .Value, not the old reference cell operators

A reference cell is the same box the compiler made for count, created by hand with ref. The Reference Cells reference describes it as a storage location for a mutable value with reference semantics, read and written through its Value property. Older code uses operators for that:

from session import fsi

# A reference cell written with the old operators, each of which gives informational message FS3370, then .Value.
fsi([
    "let hits = ref 0;;",
    "hits := !hits + 1;;",
    "incr hits;;",
    "decr hits;;",
    "hits.Value <- hits.Value + 1;;",
    "hits.Value;;",
    "#quit;;",
], args=["--nologo"])

$ dotnet fsi --nologo
> let hits = ref 0;;
val hits: int ref = { contents = 0 }

> hits := !hits + 1;;

  hits := !hits + 1;;
  -----^^

stdin(2,6): info FS3370: The use of ':=' from the F# library is deprecated. See https://aka.ms/fsharp-refcell-ops. For example, please change 'cell := expr' to 'cell.Value <- expr'.


  hits := !hits + 1;;
  --------^

stdin(2,9): info FS3370: The use of '!' from the F# library is deprecated. See https://aka.ms/fsharp-refcell-ops. For example, please change '!cell' to 'cell.Value'.

val it: unit = ()

> incr hits;;

  incr hits;;
  ^^^^

stdin(3,1): info FS3370: The use of 'incr' from the F# library is deprecated. See https://aka.ms/fsharp-refcell-ops. For example, please change 'incr cell' to 'cell.Value <- cell.Value + 1'.

val it: unit = ()

> decr hits;;

  decr hits;;
  ^^^^

stdin(4,1): info FS3370: The use of 'decr' from the F# library is deprecated. See https://aka.ms/fsharp-refcell-ops. For example, please change 'decr cell' to 'cell.Value <- cell.Value - 1'.

val it: unit = ()

> hits.Value <- hits.Value + 1;;
val it: unit = ()

> hits.Value;;
val it: int = 2

> #quit;;

Each old operator still worked, and each earned informational message FS3370, which names its replacement:

The What’s new in F# 6 page gives the reasons: reference cells are rarely needed because let mutable covers most uses, fewer operators make F# simpler to learn, and ! is easy to confuse with the not of C#. The messages are informational, not warnings, so old code keeps compiling; RFC FS-1111 also lists --nowarn:3370 for code that cannot be changed yet.

Practise: memoize a slow lookup

memoize f returns a function with the same signature as f that remembers its results, which is called memoizationmemoization: Saving the result of a function for each argument it has seen, so that a repeated call returns the saved result instead of computing it again.. The cache is a Dictionary that only the returned closure can reach, so each call of memoize makes a cache of its own. Read the script, predict the counts it prints, then compare:

open System.Collections.Generic

// memoize returns a function with the same signature as f. The Dictionary lives in the closure,
// so each memoized function has a cache of its own.
let memoize (f: 'a -> 'b) =
    let cache = Dictionary<'a, 'b>()

    fun x ->
        match cache.TryGetValue x with
        | true, saved -> saved
        | false, _ ->
            let result = f x
            cache[x] <- result
            result

// A slow lookup, standing in for a database or a web call: it counts how often it runs.
let mutable lookups = 0

let fareFrom city =
    lookups <- lookups + 1

    match city with
    | "Pune" -> 450
    | "Agra" -> 620
    | _ -> failwith $"no fare from {city}"

let cachedFare = memoize fareFrom
let trips = [ "Pune"; "Agra"; "Pune"; "Pune"; "Agra" ]

printfn "fares: %A" (trips |> List.map cachedFare)
printfn "lookups for %d trips: %d" trips.Length lookups

// A second memoized function starts with an empty cache of its own.
let otherCache = memoize fareFrom
otherCache "Pune" |> ignore
printfn "lookups after a second cache: %d" lookups

// A failure is not saved, so the next call tries again.
for _ in 1..2 do
    try
        cachedFare "Goa" |> ignore
    with ex ->
        printfn "failed: %s (lookups: %d)" ex.Message lookups

from session import fsi

# #load runs memo.fsx, then prints the signature of memoize and of the functions it made.
fsi([
    '#load "memo.fsx";;',
    "#quit;;",
], args=["--nologo"])

$ dotnet fsi --nologo
> #load "memo.fsx";;
[Loading memo.fsx]
fares: [450; 620; 450; 450; 620]
lookups for 5 trips: 2
lookups after a second cache: 3
failed: no fare from Goa (lookups: 4)
failed: no fare from Goa (lookups: 5)
module FSI_0002.Memo
val memoize: f: ('a -> 'b) -> ('a -> 'b) when 'a: equality
val mutable lookups: int
val fareFrom: city: string -> int
val cachedFare: (string -> int)
val trips: string list
val otherCache: (string -> int)

> #quit;;

Five trips needed only two lookups, one for Pune and one for Agra. A second memoized function, otherCache, has its own empty Dictionary, so its first call ran the lookup again, the third. The lookup for Goa failed twice and ran twice, because cache[x] <- result is never reached when f x throws: failures are not cached. The signature, f: ('a -> 'b) -> ('a -> 'b) when 'a: equality, carries a condition that the Dictionary key brings: the key type must support equality.

Then try the four ideas of this lesson in the self-check. It begins where your answers so far are weakest, and each option, right or wrong, comes with the reason the moment you choose it:

Interview questions

Warm-up (fresher to 2–5 years): what does an F# closure capture, and when do two closures share a value?

A closure is a function value together with the values it uses from the scope where it was created. For an immutable value it captures that value, so later code cannot change what the closure sees: three lambdas made in for i in 1..3 kept 1, 2 and 3. A let mutable local is different. A closure that uses it needs it to outlive its scope, so the compiler stores it in a reference cell (warning 3180 reports where), and the closure keeps the cell. Every closure made over that variable shares the cell and sees its latest value: three lambdas made in a while loop over one mutable i all returned 3. Each call of a function such as makeCounter creates a new cell, so separate counters stay separate.

Two harder questions follow, about callbacks that all report the same value and about rules kept in a long match:

Key takeaways

• fun x -> x * 2 is a function value without a name; it can be passed, returned, stored in a list or bound with let, exactly like a function defined with let.
• A higher-order function takes or returns functions, and a Map of names to functions is a dispatch table: adding a rule is adding an entry, and Map.tryFind handles a name that has no rule.
• A closure keeps the immutable values it captured, while a captured let mutable local becomes one reference cell that every closure over it shares, which is why closures made in a while loop all saw 3.
• Write cell.Value and cell.Value <- v instead of !, :=, incr and decr, which give informational message FS3370 since F# 6, and prefer let mutable to ref where a local will do.