Learn

F# lists are immutable, singly-linked. Combined with pattern matching and recursion, they're the central data structure for functional F#. "Real-World Functional Programming" treats them as foundational.

Creating lists

let empty = []
let xs = [1; 2; 3]                  // semicolons, NOT commas
let ys = 0 :: xs                    // 0 prepended
let combined = xs @ [4; 5]          // append (O(n) in left)

The :: operator is cons — adds an element to the front. O(1).

Range syntax

[1..5]                              // [1; 2; 3; 4; 5]
[1..2..10]                          // [1; 3; 5; 7; 9] — step 2
['a'..'e']                          // ['a'; 'b'; 'c'; 'd'; 'e']

F# has nice range syntax — handy for sequences and tests.

Pattern matching on lists

let rec length xs =
    match xs with
    | [] -> 0
    | _ :: rest -> 1 + length rest

let rec sum xs =
    match xs with
    | [] -> 0
    | x :: rest -> x + sum rest

List module — daily-use functions

List.length [1; 2; 3]                      // 3
List.head [1; 2; 3]                         // 1 — throws on empty
List.tail [1; 2; 3]                         // [2; 3]
List.tryHead []                             // None
List.rev [1; 2; 3]                          // [3; 2; 1]
List.map (fun x -> x * 2) [1; 2; 3]         // [2; 4; 6]
List.filter (fun x -> x > 2) [1; 2; 3; 4]  // [3; 4]
List.fold (+) 0 [1; 2; 3]                   // 6
List.reduce (+) [1; 2; 3]                   // 6 — no initial; throws on empty
List.iter (printfn "%d") [1; 2; 3]
List.contains 2 [1; 2; 3]                   // true
List.sortBy (fun x -> -x) [3; 1; 2]         // [3; 2; 1]
List.zip [1; 2; 3] ["a"; "b"; "c"]         // [(1, "a"); (2, "b"); (3, "c")]
List.partition (fun x -> x > 2) [1; 2; 3; 4]  // ([3; 4], [1; 2])

Tail recursion

F# has tail-call optimization on .NET — but only for SELF-recursive functions in tail position. The accumulator pattern still helps:

let sum xs =
    let rec loop acc = function
        | [] -> acc
        | x :: rest -> loop (acc + x) rest
    loop 0 xs

For production code, prefer List.fold — battle-tested, tail-recursive internally.

Pipelines

[1..10]
|> List.filter (fun x -> x % 2 = 1)
|> List.map (fun x -> x * x)
|> List.sum
// 1 + 9 + 25 + 49 + 81 = 165

The |> operator threads a value through functions — F#'s signature flow style.

Common mistakes

• Using commas instead of semicolons — [1, 2, 3] is a list of ONE tuple element, not three. Use semicolons.
• Non-tail-recursive list traversals — stack overflow on large lists. Use accumulator pattern or List.fold.
• xs @ [x] in a loop — O(n²). Build with :: and reverse at the end with List.rev.
• Mixing types in a list — F# lists are HOMOGENEOUS. [1; "a"] is a type error.
• Using head/tail directly — throws on empty. Use tryHead / tryTail or pattern-match.