Data Abstraction & Abstract Data Types

The central act of data abstraction is drawing a line. On one side of the line is the client — code that uses your type. On the other side is the implementer — code that defines it. The client sees only the interface: a collection of operation signatures and their behavioral contracts. The implementer sees the representation: the actual fields, arrays, pointers, and procedures.

This divide has a name in the literature: information hiding (Parnas, 1972). The key insight is that hiding is not about secrecy — it is about managing what changes affect what. If client code is permitted to see the representation, then every change to the representation is a breaking change for clients. If client code is forbidden from seeing the representation, the implementer can change it freely.

In Python, the convention is to prefix private fields with an underscore (_). In Java, private is enforced by the compiler. In C, you can hide a struct's definition behind a typedef in a .h file. In Haskell, you control which names a module exports. The mechanism differs, but the principle is identical: the interface is a contract; the representation is a secret.

A crucial corollary: the interface must be complete (clients need everything they legitimately need) and minimal (it should not expose implementation artifacts). An interface that leaks representation details — say, a getInternalArray() method on a Stack — defeats the whole purpose.

# BAD: client pokes into representation
class Stack:
    def __init__(self):
        self.data = []  # exposed!

s = Stack()
s.data.append(42)   # client bypasses the interface entirely
print(s.data[0])    # client assumes list representation

# GOOD: interface enforced
class Stack:
    def __init__(self):
        self._data = []   # private by convention

    def push(self, item): self._data.append(item)
    def pop(self):        return self._data.pop()
    def peek(self):       return self._data[-1]
    def is_empty(self):   return len(self._data) == 0

s = Stack()
s.push(42)
print(s.peek())   # 42 — only interface methods used

An Abstract Data Type (ADT) is a type defined by:

1. A set of values (the abstract values the type can take on, not the representations)
2. A set of operations (what you can do with values of the type)
3. Behavioral specifications for each operation (what the operation means in terms of the abstract values)

Notice: no mention of arrays, pointers, or any concrete data. An ADT is a mathematical object. The canonical example is the Stack ADT:

• Abstract values: finite sequences of elements, ε (empty), or (e₁, e₂, ..., eₙ) with eₙ as the top
• Operations: new()→Stack, push(Stack, T)→Stack, pop(Stack)→(Stack, T), peek(Stack)→T, is_empty(Stack)→Bool
• Behavioral specs: pop(push(s, e)) = (s, e), peek(push(s, e)) = e, is_empty(new()) = true, is_empty(push(s, e)) = false

These specifications are algebraic axioms — they define the type completely without reference to any implementation. This is the cleanest notion of ADT, originating with the work of Guttag and Liskov at MIT in the 1970s.

A subtler but important point: the same ADT can be implemented in many ways (array-based stack, linked-list stack, two-queue stack) and the same implementation can realize multiple ADTs (a Python list implements Stack, Queue, Deque, and Sequence ADTs, depending on which operations you expose). The ADT and the implementation are genuinely different things.

-- Haskell: the Stack ADT as a type class (pure interface)
class StackADT s where
  empty  :: s a
  push   :: a -> s a -> s a
  pop    :: s a -> (a, s a)   -- partial; undefined on empty
  peek   :: s a -> a          -- partial; undefined on empty
  isEmpty :: s a -> Bool

-- One implementation: newtype wrapping a list
newtype ListStack a = LS [a]

instance StackADT ListStack where
  empty            = LS []
  push x (LS xs)   = LS (x:xs)
  pop (LS (x:xs))  = (x, LS xs)
  peek (LS (x:_))  = x
  isEmpty (LS xs)  = null xs

-- Another implementation: same ADT, different rep (two lists for amortized O(1))
newtype BankersStack a = BS ([a], [a])
-- (implementation elided, but same type class instance)

In any concrete implementation, not every possible state of the data fields represents a valid value of the ADT. A representation invariant (rep invariant, or RI) is a predicate on the concrete representation that must be true for every value that the ADT can legitimately produce.

Think of it this way: if your ADT is a SortedList, the rep invariant is "the underlying array is sorted in non-decreasing order." A random array of integers might be a valid Python list, but it is not a valid SortedList. The rep invariant separates the space of all possible representations (a huge, unstructured universe) from the small island of representations that are actually meaningful as values of your type.

The rep invariant serves a critical proof obligation: every public operation of the ADT must preserve the rep invariant. That is, if the RI holds before the operation runs, it must hold when the operation returns. This is called RI preservation. If every operation preserves the RI, and the constructor establishes it, then by induction every reachable state of the object satisfies the RI. You now have a global guarantee from only local checks.

Documenting the rep invariant explicitly is not optional for serious engineering — it is the single most important comment you can write in an ADT implementation. Without it, the next programmer to touch the code has no idea which states are "legal" and will inadvertently break your structure.

A common mistake: forgetting that the rep invariant must hold at the boundaries of public operations, but it is permissible to violate it transiently in the middle of a private helper. This is fine and expected — intermediate steps in a restructuring can leave the rep invalid momentarily, as long as you restore it before returning.

class SortedList:
    """
    An ADT representing a sorted sequence of integers.

    Rep invariant:
        self._data is a list of integers sorted in non-decreasing order.
        Formally: for all 0 <= i < len(self._data)-1,
                  self._data[i] <= self._data[i+1]
    """
    def __init__(self):
        self._data = []  # RI: established (empty list is vacuously sorted)

    def insert(self, x: int) -> None:
        """Insert x while maintaining sorted order."""
        # bisect.insort preserves sortedness — RI maintained
        import bisect
        bisect.insort(self._data, x)
        # RI: holds on exit because bisect.insort guarantees sorted order

    def minimum(self) -> int:
        """Return the minimum element. Requires the list is non-empty."""
        return self._data[0]  # valid because RI guarantees _data[0] is min

    def _check_ri(self):
        """Debug helper: assert the rep invariant."""
        for i in range(len(self._data) - 1):
            assert self._data[i] <= self._data[i+1], (
                f"RI violated at index {i}: "
                f"{self._data[i]} > {self._data[i+1]}"
            )

While the rep invariant tells you which concrete states are valid, the abstraction function (AF) tells you what abstract value each valid concrete state represents. It is a function:

AF: {concrete states satisfying RI} → {abstract values}

This is a mathematical function, not code. You write it as a comment (or a formal spec), and it serves as the Rosetta Stone between the two worlds: given any valid state of your implementation, the abstraction function tells you what abstract value a client observing your type would see.

Example: for a Stack implemented with a Python list _data, the abstraction function is:

AF(s) = the sequence (s._data[0], s._data[1], ..., s._data[n-1]) with s._data[n-1] as the top

For a Set implemented with a sorted list, AF maps the list [1, 2, 3] to the mathematical set {1, 2, 3}.

The abstraction function also reveals an important subtlety: multiple concrete states can map to the same abstract value. For example, a Set implemented with a hash table might store {1, 2, 3} with the elements in different internal bucket positions depending on the hash values — but all of those concrete states represent the same abstract set {1, 2, 3}. This is normal and expected. The AF is not required to be injective.

The payoff: once you have stated the RI and AF precisely, you can prove correctness of each operation by showing that, if the input satisfies the RI and the AF maps it to the expected abstract value, then the output also satisfies the RI and the AF maps the output to the correct abstract result. Correctness proofs for ADTs are structured precisely this way.

A critical rule: the rep invariant and abstraction function must be written as comments in the implementation file, not the interface. They are part of the implementer's reasoning, not the client's contract.

class Fraction:
    """
    ADT for exact rational numbers.

    Representation:
        _num: int  (numerator)
        _den: int  (denominator, strictly positive)

    Rep invariant:
        self._den > 0
        gcd(abs(self._num), self._den) == 1   (always in lowest terms)

    Abstraction function:
        AF(f) = f._num / f._den   (as a mathematical rational number)
        e.g. AF(Fraction with _num=3, _den=4) = 3/4
             AF(Fraction with _num=-1, _den=2) = -1/2

    Note: AF is NOT injective — (6, 8) and (3, 4) would both map to 3/4,
    but our RI prevents (6, 8) from being a valid rep (gcd(6,8)=2 != 1).
    So in this implementation, AF IS injective (one canonical rep per value).
    """
    from math import gcd

    def __init__(self, num: int, den: int):
        if den == 0:
            raise ValueError("Denominator cannot be zero")
        from math import gcd
        sign = -1 if (num < 0) ^ (den < 0) else 1
        g = gcd(abs(num), abs(den))
        self._num = sign * abs(num) // g
        self._den = abs(den) // g
        # RI established: _den > 0 and in lowest terms

    def __add__(self, other):
        from math import gcd
        n = self._num * other._den + other._num * self._den
        d = self._den * other._den
        return Fraction(n, d)  # constructor re-normalizes, RI preserved

    def __repr__(self):
        return f"{self._num}/{self._den}"

Before ADTs, the dominant abstraction tool was procedural abstraction: hiding complexity inside a function. sort(array) hides a sorting algorithm; the caller only needs to know the pre/postconditions. This is powerful, but it only abstracts behavior. It says nothing about the data the behavior operates on.

Data abstraction goes one level deeper: it abstracts the data itself. Instead of hiding "how we sort," we hide "what a sorted collection even is." This shift has profound consequences:

1. Invariant enforcement: A procedure cannot enforce that its data is used correctly between calls. An ADT can, because all mutations go through operations that preserve the rep invariant.

2. Multiple implementations: You can swap the implementation of an ADT (e.g., replace a linked list with a skip list) without touching any client code. You cannot do this with ad-hoc data structures.

3. Reasoning locality: With an ADT, you reason about your module in isolation. With raw shared data structures, correctness of one module can depend on what every other module does to the data.

Barbara Liskov's 1974 paper introducing CLU made this distinction precise and showed that the programming language itself should enforce it — not just convention. This was a radical idea at the time. Today it is the foundation of every statically-typed object-oriented language.

The hierarchy is: expressions < procedures < data abstractions < modules. Each level encapsulates more, and each level is built on the previous. Understanding where ADTs sit in this hierarchy explains why they were such a conceptual breakthrough: they were the first abstraction mechanism that could truly manage the complexity of large-scale software.

# Procedural abstraction: hides HOW, not WHAT
def find_minimum(arr: list) -> int:
    """Returns minimum element. Client still sees and can mutate arr."""
    return min(arr)

arr = [3, 1, 4, 1, 5]
print(find_minimum(arr))  # 1
arr.sort()  # client mutates data freely — no invariants enforced
arr.append(-99)  # chaos is possible

# Data abstraction: hides WHAT the data IS
class MinTracker:
    """
    ADT: tracks a multiset of integers; supports O(1) minimum queries.
    RI: _heap satisfies the min-heap property.
    AF: the multiset of elements ever inserted minus those removed.
    """
    import heapq
    def __init__(self):
        self._heap = []

    def add(self, x: int) -> None:
        import heapq; heapq.heappush(self._heap, x)

    def get_min(self) -> int:
        return self._heap[0]  # safe ONLY because RI guarantees heap property

    def remove_min(self) -> int:
        import heapq; return heapq.heappop(self._heap)

# Client can NEVER violate the heap property — all mutations go through add/remove_min

An ADT's operations are specified using contracts: a formal statement of what the operation requires and what it guarantees. The classic formulation (due to Hoare, 1969) uses:

• Precondition (requires): what the caller must ensure before invoking the operation. If the precondition is violated, the operation is free to do anything — it's the caller's fault.
• Postcondition (ensures/effects): what the implementer guarantees if the precondition holds. May describe both the return value and changes to the object's abstract state.
• Modifies clause: which abstract values are changed (important for mutable ADTs).

This contract-style specification, popularized by Liskov & Guttag's Program Development in Java, is the standard at MIT 6.005/6.031. It is also the foundation of Eiffel's "Design by Contract" (Meyer), Java's @requires/@ensures via JML, and modern tools like Dafny and Coq.

A critical design decision: how strong should preconditions be? A total operation has the precondition true — it handles all inputs, usually by throwing an exception. A partial operation has a nontrivial precondition — it is simply undefined for invalid inputs, and the implementer can exploit this. Partial operations are more dangerous but sometimes necessary for performance (e.g., pop on a stack might require !is_empty() and simply crash otherwise).

The specification's strength also determines how easy it is to implement correctly vs. how easy it is to use safely. A very weak postcondition (e.g., sort only guarantees the result is a permutation of the input, not necessarily sorted) is easy to implement but useless. A very strong postcondition is useful but may over-constrain the implementation. Good specification design navigates this tension deliberately.

def binary_search(arr: list, target: int) -> int:
    """
    Specification:

    Requires:
        arr is sorted in non-decreasing order.
        (Precondition: caller's responsibility. Violation => undefined behavior.)

    Effects:
        Returns index i such that arr[i] == target,
        or raises ValueError if target is not in arr.

    Does not modify arr.
    """
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    raise ValueError(f"{target} not found")

# Note: the precondition (sortedness) is NOT checked — that's deliberate.
# Checking it would cost O(n), defeating the purpose of binary search.
# The contract makes it the CALLER'S obligation.

Representation exposure occurs when client code can obtain a reference to (or alias of) an object's internal representation and modify it directly, bypassing the ADT's operations and potentially violating the rep invariant. This is one of the most common and insidious bugs in object-oriented programming.

Consider a DateRange ADT backed by a list [start_date, end_date]. If the constructor stores a reference to the passed-in list directly (rather than copying it), the caller still holds a reference and can mutate it later, silently breaking the rep invariant. This is rep exposure.

The standard fixes:

1. Defensive copying: copy mutable inputs on the way in, and copy mutable outputs on the way out.
2. Immutability: use immutable types for the rep (e.g., Python tuples instead of lists), so there is nothing to alias.
3. Returning views: return read-only wrappers (e.g., collections.abc.Sequence view) that block mutation.

Benevolent mutation is the flip side: a change to the representation that does not change the abstract value the AF maps the rep to. A canonical example is memoization — caching a computed result in a field without changing the observable behavior. Or a Set that lazily compresses its internal structure. The AF maps both the pre- and post-mutation rep to the same abstract value, so from the client's perspective nothing changed. Benevolent mutations are always safe, but you should still document them explicitly so future implementers know which fields are "observable" and which are "cached computation."

from datetime import date
from typing import List

# DANGEROUS: rep exposure
class DateRange_Bad:
    def __init__(self, dates: List[date]):
        self._dates = dates  # stores the reference! caller can mutate it

    def start(self) -> date:
        return self._dates[0]

d = [date(2024, 1, 1), date(2024, 12, 31)]
dr = DateRange_Bad(d)
d[0] = date(2025, 6, 6)  # silently corrupts dr!
print(dr.start())  # 2025-06-06 — wrong!

# SAFE: defensive copying
class DateRange:
    """
    RI: len(self._dates) == 2 and self._dates[0] <= self._dates[1]
    AF: the closed interval [self._dates[0], self._dates[1]]
    """
    def __init__(self, dates: List[date]):
        self._dates = list(dates)  # defensive copy on the way IN
        assert len(self._dates) == 2 and self._dates[0] <= self._dates[1]

    def get_bounds(self) -> List[date]:
        return list(self._dates)  # defensive copy on the way OUT

d = [date(2024, 1, 1), date(2024, 12, 31)]
dr = DateRange(d)
d[0] = date(2025, 6, 6)  # has no effect on dr
print(dr.get_bounds()[0])  # 2024-01-01 — correct

One of the most fundamental design decisions for any ADT is whether it should be mutable or immutable.

An immutable ADT (also called a value type or functional type) has no operations that change the abstract value. Every operation that "modifies" the value actually returns a new value. Python's str, tuple, and frozenset; Java's String, Integer, LocalDate; and Haskell's types by default are all immutable. The advantages are profound:

• No aliasing bugs: sharing an immutable object is always safe
• Thread-safety for free: no synchronization needed
• Simple equational reasoning: x = f(y) means x has the abstract value of f applied to y, forever
• AF is simpler: no need to distinguish "before" and "after" states

A mutable ADT has operations that change the abstract value in place (push, insert, delete, assign). These are often more efficient (avoiding copies) and sometimes necessary for modeling stateful entities (a bank account, a game state, a sensor reading). But they introduce complexity:

• Aliasing: two references to the same object see each other's mutations
• Specification must describe both the return value and the mutated state
• Concurrent access requires explicit synchronization

The choice is not always obvious. Python chose to make list mutable and tuple immutable — giving programmers both options. Functional languages like Haskell make everything immutable by default and use monads to model state explicitly. Neither approach is universally superior; understanding the tradeoffs is the mark of a mature designer.

A key guideline from MIT 6.031: prefer immutability by default. Only make a type mutable when you have a clear reason (performance, modeling identity of an entity). This is because immutability eliminates an entire class of bugs (aliasing, rep exposure) at the cost of potentially more allocation — a tradeoff that usually favors correctness.

# Immutable rational number — every operation returns a new object
from math import gcd
from typing import NamedTuple

class Rat(NamedTuple):
    """Immutable rational. RI: den > 0, gcd(abs(num), den) == 1."""
    num: int
    den: int

    def __new__(cls, num: int, den: int):
        if den == 0: raise ZeroDivisionError
        sign = -1 if (num * den < 0) else 1
        g = gcd(abs(num), abs(den))
        return super().__new__(cls, sign * abs(num) // g, abs(den) // g)

    def __add__(self, other: 'Rat') -> 'Rat':
        return Rat(self.num * other.den + other.num * self.den,
                   self.den * other.den)

    def __repr__(self): return f"{self.num}/{self.den}"

a = Rat(1, 2)
b = Rat(1, 3)
print(a + b)    # 5/6 — a and b unchanged
print(a)        # 1/2 — immutable

# Aliasing is always safe:
alias = a
print(alias is a)  # True, but it doesn't matter — nothing can change a

Once you have the notion of an ADT with a precise contract, a natural question arises: when can one type be used in place of another? Barbara Liskov's answer (with Jeannette Wing, 1994) is the Liskov Substitution Principle (LSP):

If S is a subtype of T, then objects of type S may be substituted for objects of type T without altering any desirable property of the program.

More precisely, if T specifies certain pre/postconditions, then any subtype S must:

• Contravariant preconditions: S may accept more inputs than T (weaker or equal preconditions)
• Covariant postconditions: S must guarantee at least as much as T (stronger or equal postconditions)
• Behavioral compatibility: the abstract value semantics must be consistent

This is often stated as: subtypes may strengthen postconditions and weaken preconditions, but never the reverse.

The LSP is violated constantly in practice. The canonical example: if Square extends Rectangle, and Rectangle has set_width(w) which preserves height, then Square cannot satisfy this contract (setting width must also set height to maintain squareness). Despite being geometrically a subtype, Square is NOT a behavioral subtype of Rectangle in this design. This is why LSP violations feel wrong: they mean the inheritance hierarchy does not match the behavioral contract hierarchy.

LSP is the formal underpinning of interface-based polymorphism: if every implementation of an interface satisfies the same behavioral contract, you can swap implementations freely. This is exactly what dependency injection, mock objects in testing, and plugin architectures rely on.

# LSP violation: Square "extends" Rectangle but breaks the contract
class Rectangle:
    def __init__(self, w, h): self._w, self._h = w, h
    def set_width(self, w): self._w = w      # contract: height unchanged
    def set_height(self, h): self._h = h    # contract: width unchanged
    def area(self): return self._w * self._h

class Square(Rectangle):   # WRONG: violates LSP
    def set_width(self, w):
        self._w = self._h = w   # BREAKS the Rectangle contract
    def set_height(self, h):
        self._w = self._h = h   # BREAKS the Rectangle contract

def test_rectangle(r: Rectangle):
    r.set_width(5)
    r.set_height(10)
    assert r.area() == 50   # ALWAYS holds for Rectangle
    # But fails for Square: area() = 100 (both set to 10)

# Better design: separate types, or use a common interface
from abc import ABC, abstractmethod

class Shape(ABC):
    @abstractmethod
    def area(self) -> float: ...

class Rectangle(Shape):
    def __init__(self, w, h): self._w, self._h = w, h
    def area(self): return self._w * self._h

class Square(Shape):
    def __init__(self, side): self._side = side
    def area(self): return self._side ** 2
# Now Square and Rectangle implement the same ADT (Shape) without violating any contract

The most rigorous way to specify an ADT is algebraically: define the type purely by equations that its operations must satisfy, with no reference to any implementation. This approach, due to Guttag (MIT), Goguen, and others, treats ADT specification as algebra — hence the name.

The idea: classify operations into constructors (that create or build values of the type) and observers (that query values). Then write equations showing what observers return when applied to values built by constructors. These equations are the axioms of the ADT.

For a Stack<T>:

• Constructors: empty, push
• Observers: pop, peek, is_empty
• Axioms:
  • is_empty(empty()) = true
  • is_empty(push(s, e)) = false
  • peek(push(s, e)) = e
  • pop(push(s, e)) = s

These four axioms completely characterize the Stack ADT. Any implementation that satisfies all four axioms is a correct implementation, regardless of what internal data structure it uses. You can test compliance by checking the axioms directly.

The algebraic approach has deep connections to equational logic and term rewriting systems in theoretical CS. It is the foundation of property-based testing frameworks like QuickCheck (Haskell) and Hypothesis (Python), which generate random inputs and check that algebraic properties hold. Instead of writing specific test cases, you encode the axioms and let the framework search for counterexamples.

The power of algebraic specs: they are implementation-independent by construction. You can give the same spec to five different teams and each will build a different implementation, but all will be correct. This is how standard libraries and APIs should be specified.

# Algebraic spec as property-based tests using Hypothesis
from hypothesis import given, strategies as st
from hypothesis.stateful import RuleBasedStateMachine, rule, initialize

class StackMachine(RuleBasedStateMachine):
    """
    Tests the algebraic axioms of the Stack ADT.
    Any correct Stack implementation should pass these.
    """
    def __init__(self):
        super().__init__()
        self.stack = []  # using list as our Stack under test

    @rule(e=st.integers())
    def axiom_peek_after_push(self, e):
        self.stack.append(e)
        assert self.stack[-1] == e          # peek(push(s, e)) = e

    @rule(e=st.integers())
    def axiom_pop_after_push(self, e):
        before = list(self.stack)
        self.stack.append(e)
        self.stack.pop()
        assert self.stack == before         # pop(push(s, e)) = s

    @rule()
    def axiom_not_empty_after_push(self):
        import random
        e = random.randint(0, 100)
        self.stack.append(e)
        assert len(self.stack) > 0          # is_empty(push(s, e)) = false

# Run with: from hypothesis import settings; StackMachine.TestCase

The ultimate enforcement mechanism for ADT boundaries is the type system itself. Different languages occupy different points on a spectrum from "honor system" to "compiler-enforced guarantee."

Python: uses naming conventions (_private) and docstrings. Nothing prevents a client from accessing _data. Violations are not caught until runtime — or never. The ADT exists only in the programmer's mind and documentation.

Java/C++: private and protected keywords enforce the boundary at compile time. A client truly cannot call object._data — the compiler rejects it. The type system enforces the interface/implementation divide for data members and methods.

Haskell/ML module systems: a module can export a type name without exporting its constructors. Clients can use values of the type but cannot pattern-match on (or construct) its internal representation. This is the strongest form of data abstraction in mainstream languages.

Dependent type systems (Coq, Agda, Idris): the rep invariant itself can be encoded as a type. Instead of List Int (a list with no invariant), you can have SortedList Int as a type that is inhabited only by sorted lists — the type checker verifies the invariant at compile time. This is the theoretical endpoint of the abstraction journey.

Understanding this spectrum is essential: Python conventions require trust and discipline; Java private requires trust in the language implementer; Haskell modules require trust in the module system; dependent types require trust only in the logic. Each step up the stack moves more of the correctness burden from the programmer to the machine. The appropriate level depends on the stakes, the team size, and the toolchain available.

-- Haskell: opaque type via module system
-- In file Set.hs:
module Set (Set, empty, insert, member, toList) where

-- The constructor 'S' is NOT exported — clients cannot build or inspect Sets directly
newtype Set a = S [a]  -- internal rep: sorted list, no duplicates

empty :: Set a
empty = S []

insert :: Ord a => a -> Set a -> Set a
insert x (S xs)
    | x `elem` xs = S xs
    | otherwise   = S (insertSorted x xs)
  where
    insertSorted y []     = [y]
    insertSorted y (z:zs)
        | y < z     = y : z : zs
        | otherwise = z : insertSorted y zs

member :: Ord a => a -> Set a -> Bool
member x (S xs) = x `elem` xs

toList :: Set a -> [a]
toList (S xs) = xs

-- In client code:
-- import Set
-- s = insert 3 (insert 1 (insert 2 empty))
-- member 2 s  =>  True
-- Cannot write: S [3,1,2]  -- 'S' is not in scope! Type system enforces the ADT.

Many classic design patterns from the Gang of Four are, at their core, formalized ADT design decisions. Recognizing this makes both the patterns and the underlying theory more vivid.

Iterator: an ADT with has_next(): Bool and next(): T. It abstracts over the traversal order of a collection. Python's __iter__/__next__ protocol is this ADT. The client doesn't care if the backing structure is a list, a tree, a generator, or a network stream — they interact only through the iterator interface.

Comparator/Ordering: an ADT with compare(a, b): int that returns negative/zero/positive. It abstracts over "what less-than means" for a type, allowing sorting algorithms to be written without knowing the element type. This is the textbook example of separating the sorting algorithm (implementation of an algorithm ADT) from the ordering criterion (a different ADT).

Observer/Event: the observer pattern defines an ADT (EventSource) with subscribe(handler) and an implicit notify(event) operation. It abstracts over the mechanism of notification — polling vs. push, synchronous vs. asynchronous — behind a uniform interface.

Flyweight: a pattern where many objects share a common immutable part. The shared part is an immutable ADT; the unique part is mutable state. This is directly related to the immutable vs. mutable ADT design decision.

The deeper insight: most design patterns are solutions to specific ADT design problems — what interface to expose, how to separate concerns, how to make a type substitutable. Seeing patterns through the ADT lens makes them less mysterious and more principled.

# Iterator as an ADT: abstract over traversal
from typing import TypeVar, Generic, Iterator
from abc import ABC, abstractmethod

T = TypeVar('T')

# The Iterator ADT
class Traversable(ABC, Generic[T]):
    @abstractmethod
    def __iter__(self) -> Iterator[T]: ...

# Three concrete implementations of the same Traversable interface
class InOrder(Traversable[int]):
    """In-order traversal of a BST (rep hidden)."""
    def __init__(self, root): self._root = root
    def __iter__(self):
        def inorder(node):
            if node:
                yield from inorder(node.left)
                yield node.val
                yield from inorder(node.right)
        yield from inorder(self._root)

class ReverseList(Traversable[int]):
    """Reverse traversal of a list."""
    def __init__(self, data): self._data = data
    def __iter__(self): return reversed(self._data)

class Fibonacci(Traversable[int]):
    """Infinite Fibonacci sequence (a generator-backed traversable)."""
    def __iter__(self):
        a, b = 0, 1
        while True: yield a; a, b = b, a + b

# Client code works identically for all three:
def print_first_five(t: Traversable) -> None:
    for i, x in enumerate(t):
        if i == 5: break
        print(x, end=' ')
    print()