Discriminated Unions

Discriminated Unions in F#

Master discriminated unions in F# with free flashcards and spaced repetition practice. This lesson covers defining and pattern matching discriminated unions, recursive structures, and real-world applications—essential concepts for functional programming mastery in F#.

Welcome 💻

Welcome to one of F#'s most powerful features! Discriminated unions (also called algebraic data types or sum types) are a cornerstone of functional programming that allow you to model choices and alternatives in your domain precisely. Unlike classes in object-oriented languages, discriminated unions let you say "this value is one of several named cases," making your code safer, more expressive, and easier to reason about.

Think of discriminated unions as a way to create custom types that represent "either this OR that" scenarios—like a payment method that's either cash, credit card, or PayPal. The F# compiler ensures you handle every possible case, preventing entire categories of bugs.

Core Concepts 🎯

What Are Discriminated Unions?

A discriminated union defines a type with multiple named cases. Each case can optionally carry associated data of different types.

Basic syntax:

type TypeName =
    | Case1
    | Case2
    | Case3 of dataType
    | Case4 of field1:type1 * field2:type2

💡 Tip: The | symbol (pipe) introduces each case. The first | is optional but recommended for consistency.

Simple Discriminated Unions

Let's start with a union representing playing card suits:

type Suit =
    | Hearts
    | Diamonds
    | Clubs
    | Spades

These are simple cases with no associated data. You create values like this:

let mySuit = Hearts
let yourSuit = Spades

Unions with Associated Data

Cases can carry data, making them incredibly powerful:

type Shape =
    | Circle of radius:float
    | Rectangle of width:float * height:float
    | Triangle of base:float * height:float

Notice how each case carries different types and amounts of data. Creating values:

let myCircle = Circle(radius=5.0)
let myRect = Rectangle(width=10.0, height=20.0)
let myTriangle = Triangle(4.0, 6.0)  // Named parameters optional

🧠 Memory Device: Think "Discriminated = Distinct choices" - each case is distinct and the compiler discriminates (distinguishes) between them.

Pattern Matching: The Power Tool 🔧

Pattern matching is how you work with discriminated unions. It's like a switch statement on steroids—the compiler ensures you handle every case:

let area shape =
    match shape with
    | Circle(radius) -> 
        System.Math.PI * radius * radius
    | Rectangle(width, height) -> 
        width * height
    | Triangle(base', height) -> 
        0.5 * base' * height

⚠️ Important: If you forget a case, the F# compiler gives you a warning! This exhaustiveness checking prevents bugs.

💡 Tip: Use an underscore _ as a wildcard for "any other case," but use it sparingly—explicit handling is safer.

Recursive Discriminated Unions

Discriminated unions can reference themselves, perfect for tree structures and linked lists:

type IntList =
    | Empty
    | Cons of head:int * tail:IntList

This defines a list where each node (Cons) contains an integer and the rest of the list:

// Represents [1; 2; 3]
let myList = Cons(1, Cons(2, Cons(3, Empty)))

Processing recursive unions typically uses recursive functions:

let rec length list =
    match list with
    | Empty -> 0
    | Cons(_, tail) -> 1 + length tail

VISUALIZING RECURSIVE STRUCTURE

    Cons                     IntList
    ╱  ╲                    ┌────────┐
   1   Cons        =>       │ Empty  │
      ╱  ╲                  └────────┘
     2   Cons               ┌────────┐
        ╱  ╲                │ Cons   │
       3   Empty            │ ╱    ╲ │
                            │head tail│
                            └────────┘

Single-Case Unions: Type Safety Wrappers 🔒

Even one-case unions are useful for type safety:

type EmailAddress = EmailAddress of string
type CustomerId = CustomerId of int

This prevents mixing up strings and integers:

let email = EmailAddress("user@example.com")
let id = CustomerId(42)

// This won't compile - type safety!
// let oops = sendEmail id  // CustomerId is not EmailAddress

Unwrap with pattern matching:

let validateEmail (EmailAddress email) =
    email.Contains("@")

🤔 Did you know? This pattern is called "newtype" in Haskell and helps prevent primitive obsession—using raw strings/ints when domain-specific types are clearer.

Examples with Deep Explanations 💡

Example 1: Payment Processing System

Let's model different payment methods:

type PaymentMethod =
    | Cash
    | CreditCard of cardNumber:string * cvv:string
    | DebitCard of cardNumber:string * pin:string
    | DigitalWallet of provider:string * accountId:string

type PaymentResult =
    | Success of transactionId:string
    | Failure of reason:string

Now process payments with exhaustive handling:

let processPayment amount method =
    match method with
    | Cash -> 
        if amount <= 100.0 then
            Success("CASH-" + System.Guid.NewGuid().ToString())
        else
            Failure("Cash payments limited to $100")
    
    | CreditCard(number, cvv) ->
        // Simulate card validation
        if cvv.Length = 3 then
            Success("CC-" + System.Guid.NewGuid().ToString())
        else
            Failure("Invalid CVV")
    
    | DebitCard(number, pin) ->
        if pin.Length = 4 then
            Success("DB-" + System.Guid.NewGuid().ToString())
        else
            Failure("Invalid PIN")
    
    | DigitalWallet(provider, accountId) ->
        Success(sprintf "DW-%s-%s" provider accountId)

// Usage
let payment1 = processPayment 50.0 Cash
let payment2 = processPayment 200.0 (CreditCard("1234-5678-9012-3456", "123"))
let payment3 = processPayment 75.0 (DigitalWallet("PayPal", "user@email.com"))

Why this works beautifully:

• Each payment method carries exactly the data it needs
• The compiler ensures we handle every payment type
• Adding a new payment method forces us to update processPayment
• Type safety prevents passing cash where a card is expected

Example 2: Abstract Syntax Tree (AST) for Expressions

Discriminated unions shine when modeling recursive structures like expression trees:

type Expr =
    | Number of float
    | Variable of string
    | Add of Expr * Expr
    | Multiply of Expr * Expr
    | Divide of Expr * Expr
    | Power of Expr * Expr

Representing the expression: (3 + x) * 2^4

let expr = 
    Multiply(
        Add(Number 3.0, Variable "x"),
        Power(Number 2.0, Number 4.0)
    )

Now write an evaluator:

let rec evaluate (variables: Map<string, float>) expr =
    match expr with
    | Number n -> n
    | Variable name -> 
        match Map.tryFind name variables with
        | Some value -> value
        | None -> failwithf "Variable %s not found" name
    | Add(left, right) -> 
        evaluate variables left + evaluate variables right
    | Multiply(left, right) -> 
        evaluate variables left * evaluate variables right
    | Divide(left, right) -> 
        evaluate variables left / evaluate variables right
    | Power(base', exp) -> 
        (evaluate variables base') ** (evaluate variables exp)

// Test it
let vars = Map.ofList [("x", 5.0)]
let result = evaluate vars expr  // (3 + 5) * 2^4 = 8 * 16 = 128

Extending the system: Want to add subtraction? Just add a case:

type Expr =
    | Number of float
    | Variable of string
    | Add of Expr * Expr
    | Subtract of Expr * Expr  // New!
    | Multiply of Expr * Expr
    // ... other cases

The compiler immediately warns you everywhere Expr is matched that you haven't handled Subtract!

EXPRESSION TREE VISUALIZATION

       Multiply
       ╱      ╲
      ╱        ╲
    Add       Power
   ╱  ╲       ╱   ╲
  3    x     2     4

  Evaluates bottom-up:
  1. Leaf nodes: 3, x, 2, 4
  2. Add: 3 + 5 = 8
  3. Power: 2^4 = 16
  4. Multiply: 8 * 16 = 128

Example 3: Option Type Deep Dive

F#'s built-in Option<'T> is a discriminated union:

type Option<'T> =
    | Some of 'T
    | None

It represents "a value that might not exist" without null references:

let tryDivide x y =
    if y = 0.0 then
        None
    else
        Some(x / y)

let result1 = tryDivide 10.0 2.0  // Some 5.0
let result2 = tryDivide 10.0 0.0  // None

Chaining operations safely:

let safeSqrt x =
    if x < 0.0 then None
    else Some(sqrt x)

let safeOperation x =
    tryDivide 100.0 x
    |> Option.bind safeSqrt  // Only continues if previous returned Some
    |> Option.map (fun result -> result * 2.0)  // Transform inner value

let test1 = safeOperation 4.0   // Some 10.0 (sqrt(100/4) * 2 = 5 * 2)
let test2 = safeOperation 0.0   // None (division by zero)
let test3 = safeOperation -5.0  // None (negative sqrt)

Why Option beats null:

• Explicit in the type signature: string option vs string (which might be null?)
• Compiler forces you to handle both cases
• No NullReferenceException surprises

Example 4: Result Type for Error Handling

The Result<'T,'TError> type models success or failure:

type Result<'T,'TError> =
    | Ok of 'T
    | Error of 'TError

Using it for validation:

type ValidationError =
    | EmptyString
    | TooShort of minLength:int
    | TooLong of maxLength:int
    | InvalidCharacters of chars:string

let validateUsername (username: string) : Result<string, ValidationError list> =
    let errors = [
        if System.String.IsNullOrWhiteSpace(username) then
            yield EmptyString
        if username.Length < 3 then
            yield TooShort(minLength=3)
        if username.Length > 20 then
            yield TooLong(maxLength=20)
        if not (username |> Seq.forall System.Char.IsLetterOrDigit) then
            yield InvalidCharacters("Only letters and numbers allowed")
    ]
    
    if errors.IsEmpty then
        Ok username
    else
        Error errors

// Test cases
let valid = validateUsername "john123"     // Ok "john123"
let invalid1 = validateUsername "ab"       // Error [TooShort 3]
let invalid2 = validateUsername "user@123" // Error [InvalidCharacters ...]

Processing results:

let formatError error =
    match error with
    | EmptyString -> "Username cannot be empty"
    | TooShort min -> sprintf "Username must be at least %d characters" min
    | TooLong max -> sprintf "Username cannot exceed %d characters" max
    | InvalidCharacters msg -> msg

let displayValidation result =
    match result with
    | Ok username -> 
        printfn "✓ Username '%s' is valid" username
    | Error errors -> 
        printfn "✗ Validation failed:"
        errors |> List.iter (formatError >> printfn "  - %s")

Common Mistakes ⚠️

Mistake 1: Forgetting to Handle All Cases

❌ Wrong:

let describe shape =
    match shape with
    | Circle(r) -> sprintf "Circle with radius %.2f" r
    | Rectangle(w, h) -> sprintf "Rectangle %.2f x %.2f" w h
    // Forgot Triangle! Compiler warning!

✅ Right:

let describe shape =
    match shape with
    | Circle(r) -> sprintf "Circle with radius %.2f" r
    | Rectangle(w, h) -> sprintf "Rectangle %.2f x %.2f" w h
    | Triangle(b, h) -> sprintf "Triangle base %.2f height %.2f" b h

💡 Tip: Never ignore compiler warnings about incomplete pattern matches—they prevent runtime bugs!

Mistake 2: Using Wildcard Too Eagerly

❌ Wrong:

let processPayment method =
    match method with
    | Cash -> handleCash()
    | _ -> handleCard()  // Too broad! Misses DebitCard vs CreditCard distinction

✅ Right:

let processPayment method =
    match method with
    | Cash -> handleCash()
    | CreditCard(num, cvv) -> handleCreditCard num cvv
    | DebitCard(num, pin) -> handleDebitCard num pin
    | DigitalWallet(provider, id) -> handleWallet provider id

Mistake 3: Not Using Named Fields

❌ Confusing:

type Person = Person of string * int * string  // Which is which?

✅ Clear:

type Person = Person of name:string * age:int * email:string

Named fields make pattern matching self-documenting:

let greet (Person(name=n, age=a, email=_)) =
    sprintf "Hello %s, you are %d years old" n a

Mistake 4: Confusing Union Cases with Records

❌ Wrong thinking: "Discriminated unions are like classes"

Discriminated unions represent choices (OR), records represent combinations (AND):

// Record: A person has ALL these fields
type PersonRecord = { Name: string; Age: int; Email: string }

// Union: A message is ONE of these types
type Message =
    | Email of recipient:string * subject:string
    | SMS of phoneNumber:string * text:string
    | Push of deviceId:string * title:string

🧠 Memory Device: Records AND, Unions OR - records combine fields, unions separate alternatives.

Mistake 5: Not Leveraging Type Safety

❌ Missing opportunity:

let sendEmail (email: string) = (* ... *)
let sendEmail (userId: string) = (* ... *)  // Same type, easy to mix up!

✅ Type-safe:

type Email = Email of string
type UserId = UserId of string

let sendEmail (Email email) = (* ... *)
let sendEmail (UserId id) = (* ... *)  // Compiler prevents mixing!

Key Takeaways 🎯

1. Discriminated unions model choices: Use them when a value can be one of several alternatives
2. Pattern matching is exhaustive: The compiler ensures you handle all cases
3. Each case can carry different data: Perfect for modeling diverse scenarios
4. Recursive unions enable trees and lists: Self-referential unions create powerful data structures
5. Single-case unions add type safety: Wrap primitives to prevent mixing up similar types
6. Option and Result are discriminated unions: They eliminate null references and model success/failure
7. Name your fields: Makes code self-documenting and pattern matching clearer
8. Compiler is your friend: Warnings about incomplete matches prevent bugs

🔧 Try this: Create a discriminated union for a traffic light system with Red, Yellow, and Green cases. Write a function that determines the next state and how long to wait.

📚 Further Study

1. Microsoft F# Language Reference - Discriminated Unions: https://learn.microsoft.com/en-us/dotnet/fsharp/language-reference/discriminated-unions
2. F# for Fun and Profit - Algebraic Types: https://fsharpforfunandprofit.com/posts/discriminated-unions/
3. Real World F# - Domain Modeling Made Functional: https://pragprog.com/titles/swdddf/domain-modeling-made-functional/

🌍 Real-world analogy: Think of discriminated unions like a vending machine selection panel. You can choose Snack, Drink, or Sandwich—each choice requires different handling (temperature, dispensing mechanism) and carries different data (row/column position). The machine's logic must handle all possibilities, just like pattern matching handles all union cases!