Lists and Sequences

Analogy categoryAnalogies

The F# list Type: An Immutable Singly Linked List

An F# list is an immutable singly linked list built from two cases: the empty list [] and a cons cell head :: tail, which prepends a single element onto an existing list. Because the type is immutable, operations like "let ys = 0 :: xs" don't modify xs at all -- they build a brand-new list that happens to share its tail structurally with xs, which is both memory-efficient and safe to do without defensive copying.

🏏

Cricket analogy: A scorecard entry that adds a new over on top of the existing innings record without altering any previously recorded overs mirrors 0 :: xs, which prepends a new head onto xs while leaving the original list completely untouched.

fsharp

// Cons cell construction and pattern matching
let rec sum xs =
    match xs with
    | [] -> 0
    | head :: tail -> head + sum tail

let numbers = [1; 2; 3; 4; 5]
printfn "%d" (sum numbers)          // 15

// map / filter / fold pipeline
let result =
    numbers
    |> List.filter (fun n -> n % 2 = 0)
    |> List.map (fun n -> n * n)
    |> List.fold (+) 0
printfn "%d" result                  // 20  (4 + 16)

// List comprehension with inline filtering
let multiplesOfThree = [ for i in 1..20 do if i % 3 = 0 then yield i ]

// Lazy, potentially infinite sequence
let squares = Seq.initInfinite (fun i -> i * i)
let firstFiveSquares = squares |> Seq.take 5 |> Seq.toList
printfn "%A" firstFiveSquares        // [0; 1; 4; 9; 16]

Transforming Lists: map, filter, fold

List.map, List.filter, and List.fold are the three workhorses for transforming lists: map applies a function to every element and returns a new list of the same length, filter keeps only elements satisfying a predicate, and fold combines every element into a single accumulated result by threading an accumulator through the list from left to right, as in "List.fold (+) 0 [1;2;3]" which yields 6. Because none of these mutate the original list, chaining them together is always safe and predictable.

🏏

Cricket analogy: Reviewing an innings by first filtering out dot balls, then mapping each scoring shot to its run value, then folding all those runs into a single total mirrors List.filter |> List.map |> List.fold, each stage transforming the data toward one final number.

List.fold and List.reduce both combine a list into a single value, but reduce uses the list's first element as the initial accumulator and throws on an empty list, while fold requires an explicit seed value and works safely on [], returning the seed unchanged.

List and Range Expressions

Range expressions like [1..10] and [1..2..20] (start, step, end) construct list literals directly, and list comprehensions extend this with for/in/yield-style syntax, as in "[for i in 1..5 -> i * i]", which produces [1; 4; 9; 16; 25] by evaluating the body once per iteration of the range. Comprehensions can also include filtering conditions inline, such as "[for i in 1..20 do if i % 3 = 0 then yield i]", to build a filtered list without a separate List.filter pass.

🏏

Cricket analogy: Generating a fixture list for a T20 tournament by listing match days 1 through 20, then filtering to only weekend dates, mirrors [for i in 1..20 do if i % 7 = 0 || i % 7 = 6 then yield i], a range with inline filtering.

seq<'T>: Lazy, Deferred Sequences

A seq<'T> (an alias for System.Collections.Generic.IEnumerable<'T>) is lazily evaluated and potentially infinite, computing each element only when it's actually requested during enumeration, unlike a list, which is fully realized in memory the moment it's constructed. This makes seq the right choice for representing something like "Seq.initInfinite (fun i -> i * i)", an infinite sequence of squares that would be impossible to represent as an eagerly-built list.

🏏

Cricket analogy: A ball-by-ball radio commentary describes each delivery only as it happens, never precomputing the whole innings in advance, mirroring how a seq computes each element only when the enumerator actually requests it.

A seq built from a side-effecting generator (such as one that reads a file or increments a counter) recomputes those side effects every time it is enumerated, because sequences are lazy and not cached by default -- enumerating the same seq twice can produce different results or double the side effects. Call Seq.toList or Seq.cache if you need to enumerate the same data more than once safely.

Choosing Between list, seq, and array

Choosing among list, seq, and array comes down to access patterns and memory tradeoffs: use list for small-to-medium collections you build recursively and pattern-match with head :: tail, use array ('T[]) when you need O(1) random access or mutation and are working with a fixed size, and use seq when the data source is large, potentially infinite, or expensive to fully materialize, such as streaming lines from a file or paginated API results.

🏏

Cricket analogy: Choosing between a printed physical scorecard (fixed, indexable) and a live-updating scoreboard feed (streaming, unbounded) mirrors choosing between array for fixed indexed data and seq for a large or unbounded stream.

An F# list is an immutable singly linked list built from [] and head :: tail cons cells.
List.map, List.filter, and List.fold transform lists without mutating the original.
Range expressions ([1..10]) and comprehensions ([for i in ... -> ...]) build list literals concisely.
seq<'T> is lazily evaluated and can represent infinite sequences that a list cannot.
Re-enumerating a side-effecting seq can re-trigger those side effects; use Seq.cache or Seq.toList to avoid it.
array gives O(1) random access and in-place mutation, unlike list.
Choose list for recursive processing, array for random access, and seq for large or infinite data.