F# Guide — Lists: Ordered Collections of Elements

In this tutorial, you will learn about F# Guide. We cover key concepts, practical examples, and best practices to help you master this topic.

F# lists are immutable, singly-linked, ordered collections that support efficient prepend operations and come with a comprehensive set of built-in functions for transformation, filtering, and aggregation.

What You'll Learn

• Creating and working with lists
• List patterns: head, tail, cons
• Map, filter, and fold operations
• List comprehensions and generation
• Performance characteristics

Why It Matters

Lists are the most commonly used collection in F#. Mastering list operations is essential for writing idiomatic F# code. Durga Antivirus Pro uses lists for processing scan results and rule chains.

Real-World Use

Lists are used for sequences of data in data processing pipelines, configuration items, event logs, and any ordered collection of elements.

flowchart LR
    A["Lists"] --> B["Construction"]
    B --> C["Patterns"]
    C --> D["Transformations"]
    D --> E["Performance"]
    A:::current --> B
    style A fill:#2563eb,stroke:#2563eb,color:#fff
    style B fill:#dbeafe,stroke:#2563eb,color:#1e40af
    style C fill:#dbeafe,stroke:#2563eb,color:#1e40af
    style D fill:#dbeafe,stroke:#2563eb,color:#1e40af
    style E fill:#f1f5f9,stroke:#94a3b8,color:#64748b

Creating Lists

// Literal syntax
let empty = []
let numbers = [1; 2; 3; 4; 5]
let strings = ["apple"; "banana"; "cherry"]

// Range syntax
let range = [1..10]
let stepped = [0..2..20]  // [0; 2; 4; ...; 20]

// List comprehension
let squares = [for i in 1..10 -> i * i]

// Cons operator
let list = 1 :: [2; 3; 4]  // [1; 2; 3; 4]

List Properties

let list = [1; 2; 3]

List.length list   // 3
List.head list     // 1 (first element)
List.tail list     // [2; 3] (everything except first)
List.isEmpty list  // false
List.item 1 list   // 2 (indexed access - O(n))

Pattern Matching on Lists

let rec sumList lst =
    match lst with
    | [] -> 0
    | head :: tail -> head + sumList tail

let describe lst =
    match lst with
    | [] -> "Empty"
    | [x] -> sprintf "One item: %d" x
    | [x; y] -> sprintf "Two items: %d and %d" x y
    | x :: _ -> sprintf "List starting with %d" x

Map (Transform)

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

let doubled = numbers |> List.map (fun x -> x * 2)
// [2; 4; 6; 8; 10]

let strings = numbers |> List.map string
// ["1"; "2"; "3"; "4"; "5"]

Filter (Select)

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

let evens = numbers |> List.filter (fun x -> x % 2 = 0)
// [2; 4; 6]

let gt3 = numbers |> List.filter (fun x -> x > 3)
// [4; 5; 6]

Fold (Aggregate)

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

// Fold left
let sum = numbers |> List.fold (fun acc x -> acc + x) 0
// 15

// Fold back (right fold)
let concat = numbers |> List.foldBack (fun x acc -> x :: acc) []
// [1; 2; 3; 4; 5]

// Specialized folds
let total = numbers |> List.sum
let product = numbers |> List.reduce (*)

Common Operations

let list = [3; 1; 4; 1; 5; 9]

List.sort list          // [1; 1; 3; 4; 5; 9]
List.rev list           // [9; 5; 1; 4; 1; 3]
List.distinct list      // [3; 1; 4; 5; 9]
List.append list [10]   // [3; 1; 4; 1; 5; 9; 10]
List.concat [[1;2]; [3;4]]  // [1; 2; 3; 4]
List.chunkBySize 2 list // [[3; 1]; [4; 1]; [5; 9]]

List Generation

// Generate with unfold
let fibonacci =
    Seq.unfold (fun (a, b) -> Some(a, (b, a + b))) (0, 1)
    |> Seq.take 10
    |> List.ofSeq

// Initialize with function
let randomNumbers = List.init 5 (fun _ -> System.Random().Next(100))

Performance

// Lists are O(1) for prepend, O(n) for indexed access
// Prefer pattern matching and recursion over indexing

// Efficient: prepend (cons)
let efficient = 0 :: [1; 2; 3]

// Slow: append
let slow = [1; 2; 3] @ [4; 5; 6]  // O(n)

// For random access, use arrays

Common Mistakes

1. Using @ (append) in loops

Appending to a list with @ in a loop is O(n^2). Prepend with :: and reverse at the end.

2. Index-based access

Lists are linked lists. List.item is O(n). Use arrays for indexed access.

3. Forgetting lists are immutable

List.map returns a new list. The original is unchanged.

4. Ignoring tail Recursion

Recursive functions on large lists must be tail-recursive to avoid stack overflow.

5. Overusing List.ofSeq

Converting between collections has cost. Use the appropriate collection for your use case.

Practice Questions

1. What is the cons operator ::? It prepends an element to a list: 1 :: [2; 3] produces [1; 2; 3]. O(1) operation.

2. What is the difference between List.map and List.filter? List.map transforms every element. List.filter selects elements matching a condition.

3. Why is @ (append) slow? It traverses the entire first list to link its last element to the second list. O(n) per operation.

Challenge: Write a function that takes a list of numbers and returns a new list with only the prime numbers using list operations.

FAQ

{{< faq question="Are F# lists like C# lists?" >}} No. F# lists are immutable singly-linked lists. C# List is a mutable array-backed list. For C#-like lists, use ResizeArray<T> in F#. {{< /faq >}}

{{< faq question="When should I use arrays instead of lists?" >}} Use arrays for indexed access, mutable requirements, or performance-critical code. Use lists for functional transformations and prepend-heavy operations. {{< /faq >}}

{{< faq question="What is List.collect?" >}} List.collect maps each element to a list and concatenates the results. Also known as flatMap. {{< /faq >}}

{{< faq question="Can lists be infinite?" >}} No, lists are finite. Use sequences (seq) for potentially infinite collections. {{< /faq >}}

{{< faq question="How do I convert between lists and other collections?" >}} Use List.ofArray, List.ofSeq, List.toArray, List.toSeq for conversions. {{< /faq >}}

Mini Project

Build a function that processes a list of transactions and computes running balance:

type Transaction = { Date: string; Amount: float; Description: string }

let transactions = [
    { Date = "2024-01-01"; Amount = 1000.0; Description = "Deposit" }
    { Date = "2024-01-02"; Amount = -50.0; Description = "Groceries" }
    { Date = "2024-01-03"; Amount = -20.0; Description = "Gas" }
]

let runningBalances txns =
    txns
    |> List.scan (fun bal txn -> bal + txn.Amount) 0.0
    |> List.tail  // Skip initial 0

// Result: [1000.0; 950.0; 930.0]

What's Next

Now that you understand lists, explore arrays for indexed access and mutable collections.