Algebraic Data Types — Interview Q&A¶

Roadmap: Functional Programming → Algebraic Data Types

An ADT is a type built by combining other types two ways: product ("this and that", a struct/record) and sum ("this or that", a tagged union). Pattern matching takes them apart. The payoff is that you can shape the type so that illegal states cannot be written down.

A bank of 45+ questions and answers spanning definitions, domain modeling, the senior moves ("make illegal states unrepresentable", "parse, don't validate", the Expression Problem), and the deep mechanics (type counting, memory layout, match compilation). Examples are in Java, Rust, Python, and Go, with Haskell asides where the pure form clarifies. Use the <details> toggles to self-quiz: read the question, answer out loud, then expand.

Table of Contents¶

1. Fundamentals / Junior
2. Intermediate / Middle
3. Senior — Design with the Type System
4. Professional / Deep — Counting, Layout, Compilation
5. Code-Reading — Model It / Spot the Impossible State
6. Curveballs
7. Rapid-Fire / One-Liners
8. How to Talk About ADTs in Interviews
9. Summary
10. Related Topics

Fundamentals / Junior¶

Definitions, the two type constructors, and the everyday Option/Result you already use.

Q1. What is an algebraic data type?

Q2. Product type vs sum type — give a concrete example of each.

Q3. Why is it called "algebraic"?

Q4. What is Option / Optional / Maybe, and what problem does it solve?

fn find(id: u32) -> Option<User>      // the absence is in the type
match find(1) { Some(u) => greet(u), None => prompt_signup() }

Q5. What is Result / Either, and how does it differ from Option?

Q6. What is pattern matching and why is it the natural way to consume a sum type?

Q7. Show the same Shape sum type in Rust and the closest equivalent in Java.

enum Shape {
    Circle { radius: f64 },
    Rect   { w: f64, h: f64 },
}
fn area(s: &Shape) -> f64 {
    match s {
        Shape::Circle { radius } => std::f64::consts::PI * radius * radius,
        Shape::Rect { w, h }     => w * h,
    }
}

sealed interface Shape permits Circle, Rect {}
record Circle(double radius) implements Shape {}
record Rect(double w, double h) implements Shape {}

double area(Shape s) {
    return switch (s) {                      // exhaustive — compiler checks
        case Circle c -> Math.PI * c.radius() * c.radius();
        case Rect r   -> r.w() * r.h();
    };
}

Q8. Is a Java enum an algebraic data type?

Q9. What's wrong with modeling "a circle or a rectangle" as a struct with nullable fields?

type Shape struct { Kind string; Radius float64; W, H float64 } // bad

Q10. What does "exhaustive" matching mean and why do you want it?

Q11. What is the "unit" type and the "never"/"empty" type, in ADT terms?

Q12. Do Python and Go have algebraic data types?

Intermediate / Middle¶

Domain modeling, choosing Option over null, recursive ADTs, and the per-language idioms.

Q13. Why prefer Option<T> over a nullable T?

Q14. Walk through modeling a domain with ADTs. Take "a payment method".

enum PaymentMethod {
    Card    { number: CardNumber, expiry: Expiry, cvv: Cvv },
    BankXfer{ iban: Iban },
    Cash,                                  // carries no data
    GiftCard{ code: GiftCardCode, balance: Money },
}

Q15. What is a recursive ADT? Give an example.

enum Tree {
    Leaf(i32),
    Node(Box<Tree>, Box<Tree>),   // Box = heap pointer, needed for a finite size
}

Q16. How do you model sum types in Go, which has none?

type Shape interface { isShape() }
type Circle struct{ R float64 }; func (Circle) isShape() {}
type Rect   struct{ W, H float64 }; func (Rect) isShape() {}

Q17. How do you model sum types idiomatically in Python?

from dataclasses import dataclass

@dataclass(frozen=True)
class Circle: radius: float
@dataclass(frozen=True)
class Rect:   w: float; h: float

Shape = Circle | Rect              # the sum

def area(s: Shape) -> float:
    match s:
        case Circle(radius=r): return 3.14159 * r * r
        case Rect(w=w, h=h):   return w * h

Q18. Option has map and and_then/flatMap. When do you use which?

Q19. When should you NOT reach for Option/Result and just throw an exception (or panic)?

Q20. Compare error handling: Rust Result + ? vs Go if err != nil vs Java checked exceptions.

Q21. What combinators exist on Result, and how do you compose a fallible pipeline?

fn load(path: &str) -> Result<Config, Error> {
    let raw = read_file(path)?;          // ? = propagate Err, unwrap Ok
    let txt = String::from_utf8(raw).map_err(Error::Encoding)?;
    parse_config(&txt).map_err(Error::Parse)
}

Q22. How do Option and Result interconvert, and why would you?

Q23. What's the value of putting an invariant into the type of a variant's field rather than checking it at runtime?

Senior — Design with the Type System¶

Making illegal states unrepresentable, parse-don't-validate, the Expression Problem, and evolving ADTs.

Q24. Explain "make illegal states unrepresentable." Give a before/after.

struct Conn { connected: bool, session_id: Option<String>, error: Option<String> }
// illegal but representable: connected=true with session_id=None; or both error AND session set

enum Conn {
    Disconnected,
    Connecting,
    Connected { session_id: String },   // session ALWAYS present when connected
    Failed { error: String },           // error ONLY exists in the failed state
}

Q25. Relate the algebra of types to "make illegal states unrepresentable."

Q26. What is "parse, don't validate"?

Q27. "Parse, don't validate" vs ordinary input validation — what actually changes?

Q28. What is the Expression Problem, and how do ADTs and OO class hierarchies sit on opposite sides?

Q29. So when should I use a sum type vs a polymorphic class hierarchy?

Q30. Why does adding an enum variant break existing code — and why is that a good thing?

Q31. How do you evolve / version an ADT in a wire format or public API without breaking consumers?

Q32. Sum types over deeply-nested booleans — defend the refactor to a skeptical reviewer.

Q33. How do generics interact with ADTs — what is a parametric (generic) ADT?

Professional / Deep — Counting, Layout, Compilation¶

Type isomorphisms, memory representation, niche optimization, and how a match becomes machine code.

Q34. How many values does (Bool, Bool) have? How many does Maybe Bool (Option<bool>) have?

Q35. What's a type isomorphism, and can you give one from the algebra?

Q36. How is a sum type laid out in memory, and what is "niche" optimization?

Q37. So is Option<T> always free? When does it cost?

Q38. How does a compiler turn a match into efficient code?

Q39. Why can't you have a Tree ADT without indirection (a pointer/box) in a language like Rust or C?

Q40. What does the "function type" correspond to in the algebra of types, and why is the notation B^A?

Code-Reading — Model It / Spot the Impossible State¶

You're shown a snippet; model it as an ADT, or find the state the type lets you build but the domain forbids.

Q41. Spot the impossible state this Java class permits, then fix it with an ADT.

class HttpResponse {
    int status;           // 0 if not set yet
    String body;          // null while in flight
    String errorMessage;  // null unless failed
    boolean inFlight;
}

sealed interface HttpResponse permits InFlight, Success, Failed {}
record InFlight() implements HttpResponse {}
record Success(int status, String body) implements HttpResponse {}
record Failed(int status, String errorMessage) implements HttpResponse {}

Q42. Model this Go tagged struct as a proper sum (sealed interface) and say what you gained.

type Event struct {
    Type    string // "click", "scroll", "key"
    X, Y    int    // only for click
    DeltaY  int    // only for scroll
    KeyCode int    // only for key
}

type Event interface{ isEvent() }

type Click struct{ X, Y int };  func (Click) isEvent()  {}
type Scroll struct{ DeltaY int }; func (Scroll) isEvent() {}
type Key struct{ KeyCode int };  func (Key) isEvent()    {}

func handle(e Event) {
    switch e := e.(type) {
    case Click:  /* use e.X, e.Y */
    case Scroll: /* use e.DeltaY */
    case Key:    /* use e.KeyCode */
    default:     panic("unhandled event")   // Go has no exhaustiveness check
    }
}

Q43. This Python function re-validates the same data three times. Refactor it to "parse, don't validate".

def handle(raw: str):
    if not is_valid_email(raw): raise ValueError
    send_welcome(raw)            # re-checks raw inside
    store(raw)                   # re-checks raw inside again

from dataclasses import dataclass

@dataclass(frozen=True)
class Email:
    value: str
    @staticmethod
    def parse(raw: str) -> "Email | None":
        return Email(raw) if is_valid_email(raw) else None

def handle(raw: str):
    email = Email.parse(raw)
    if email is None: raise ValueError
    send_welcome(email)   # takes Email — no re-check possible or needed
    store(email)          # same

Q44. Read this Rust and say what the wildcard arm costs you.

enum Cmd { Start, Stop, Pause }
fn label(c: Cmd) -> &'static str {
    match c {
        Cmd::Start => "start",
        _          => "other",      // <-- 
    }
}

Q45. This Java models a card with Optional fields. What's the smell and the ADT fix?

record DiscountCode(
    Optional<Double> percentOff,
    Optional<Double> amountOff,
    Optional<Integer> freeShippingThreshold) {}

sealed interface Discount permits Percent, Amount, FreeShipping {}
record Percent(double pct) implements Discount {}
record Amount(double money) implements Discount {}
record FreeShipping(int threshold) implements Discount {}

Curveballs¶

The questions designed to catch glib answers.

Q46. Why is it called "algebraic" — in one breath?

Q47. Does Go have sum types? Pin down the honest answer.

Q48. How many values does Either<Void, Bool> have, where Void is the empty type?

Q49. ADTs vs OO class hierarchies — which "wins," and what does the Expression Problem say about the question?

Q50. Adding an enum variant broke fifty files. Isn't that terrible ergonomics?

Q51. If Option<T> is "just" null with a wrapper, why bother — isn't it the same at runtime?

Q52. Can you model an infinitely-large set of values with a finite ADT definition?

Rapid-Fire / One-Liners¶

Crisp answers; what an interviewer wants in one or two sentences.

Q53. Product vs sum, in one line each?

Q54. Option vs Result in one line?

Q55. Values in Bool × Bool? In Maybe Bool?

Q56. One sentence: "make illegal states unrepresentable"?

Q57. "Parse, don't validate" in one sentence?

Q58. The Expression Problem in one sentence?

Q59. Why is Option<&T> zero-cost?

Q60. Does Go have sum types?

Q61. Why is a wildcard _ arm risky on a domain enum?

Q62. What does a function type count as in the algebra?

How to Talk About ADTs in Interviews¶

A few habits separate a strong answer from a textbook recital:

• Lead with the guarantee, not the syntax. Don't just say "I'd use an enum." Say what becomes impossible — "the connected-but-no-session state can't be constructed, so no consumer has to defend against it." The value of an ADT is the bug class it deletes.
• Reach for the algebra when reasoning about correctness. Counting inhabitants ("3 booleans = 8 states for a 3-state domain → 5 illegal") is a concrete, senior way to justify a refactor and to explain "make illegal states unrepresentable."
• Name the trade-off. Sums give exhaustiveness inside a binary but are not forward-compatible across versioned wire formats; "parse, don't validate" needs a private constructor to hold; niche optimization is free for &T/NonZero but not for u64. Acknowledging the other side is the senior signal.
• Frame the OO comparison as the Expression Problem. "Which grows — kinds or operations?" beats a tribal "FP vs OO." It shows you understand the duality, not a slogan.
• Treat the "adding a variant broke everything" as a feature. The compiler enumerating every affected site is the safety you bought; the scary version is the one that compiles silently.
• Go deep only when invited. Memory layout, niche optimization, jump-table compilation, and B^A exponentials are great for "go deeper" prompts but shouldn't bury the practical point.
• Use a concrete domain. Modeling a payment method, an HTTP response lifecycle, or a discount as a sum lands far harder than reciting "product and sum types."

Summary¶

• An ADT is built from products (fields combined — "and") and sums (alternatives — "or"), consumed by pattern matching; "algebraic" is literal — value counts multiply for products and add for sums, with 0 (empty type) and 1 (unit type) and B^A (functions) completing a semiring.
• The junior bar is the vocabulary plus everyday Option/Result; the middle bar is domain modeling, choosing Option over null, recursive ADTs, and the per-language idioms (Rust enum, Java sealed+record, Python dataclass-union+match, Go sealed interface — with no Go sum types and no Go exhaustiveness).
• The senior bar is designing with the type system: make illegal states unrepresentable (shrink cardinality to the domain), parse don't validate (carry the proof in a narrower type), the Expression Problem (ADTs ease operations, hierarchies ease variants), and evolving/versioning ADTs (exhaustiveness helps in one binary, needs an escape hatch across wire boundaries).
• The professional bar is the mechanics: type-counting isomorphisms, tagged-union layout and niche optimization (Option<&T> is zero-cost; Option<u64> is not), why recursive ADTs need indirection, and how a match lowers to jump tables / decision trees.
• The recurring senior insight: an ADT's worth is the illegal states it deletes at compile time — judge the design by what it makes unrepresentable, and let the algebra (count the inhabitants) guide the modeling.

Related Topics¶

• junior.md — products, sums, and reading Option/Result.
• middle.md — domain modeling and the per-language idioms.
• senior.md — illegal states, parse-don't-validate, the Expression Problem.
• professional.md — type counting, memory layout, match compilation.
• Functional Programming roadmap — the paradigm these types come from.
• Map / Filter / Reduce and Composition (sibling FP topics) — the combinators that consume ADTs like Option/Result.
• Monads — Plain English (sibling FP topic) — why Option/Result/Promise share map/flatMap and are all one idea.
• Functional vs OO in Practice (sibling FP topic) — the Expression Problem trade-off in daily use.
• Clean Code → Pure Functions — total functions over precisely-shaped inputs.