2. Declarative Programming Techniques

"The nice thing about declarative programming is that you can write a specification and run it as a program. The nasty thing about declarative programming is that some clear specifications make incredibly bad programs. The hope of declarative programming is that you can move from a specification to a reasonable program without leaving the language."
- The Craft of Prolog, Richard O’Keefe

In the last chapter, we surveyed the landscape of programming paradigms. Our deep dive begins here, with the declarative model - the simplest and most predictable of them all.

An operation is declarative if it always returns the same result for the same arguments, regardless of when or how many times it is called. Think of it like a mathematical function: sin(π/2) is always 1. Declarative operations are:

  • Independent: They don't affect anything outside of themselves (no side effects).
  • Stateless: They have no memory of past calls.
  • Deterministic: Their output is completely determined by their input.

Why Start Here?

Declarative programming is the bedrock of many advanced concepts. It is the foundation of functional programming and forms a crucial, manageable subset of almost every other paradigm. Mastering it provides two key advantages:

  1. Compositionality: Declarative components are like LEGO bricks. Because they are independent and predictable, you can build them, test them in isolation, and snap them together with confidence, knowing they won't have unexpected side effects on each other.
  2. Simple Reasoning: You can reason about declarative programs with simple logic, much like solving an algebraic equation. You can replace a function call with its result without changing the program's meaning, a property called referential transparency.

Of course, not all problems are a natural fit for a purely declarative solution. But by making as many components of our programs as possible declarative, we isolate complexity and make our systems easier to build, test, and maintain.

In this chapter, we will explore the core techniques for writing practical declarative programs in Python. We will start with recursion as our fundamental tool for control flow, learn to work with immutable data structures, abstract our patterns with higher-order functions and comprehensions, and finally, package our logic into formal Abstract Data Types.

Table of contents

Topic 1: Recursion

1. Thinking Recursively

In the imperative programming you may be used to, repetition is handled by for and while loops. These constructs explicitly describe the step-by-step mechanics of an action: initialize a counter, check a condition, increment the counter, and repeat.

In the declarative world, we strive to avoid describing step-by-step mechanics. Our primary tool for repetition is recursion: the process of a function calling itself to solve a problem. A recursive function breaks a problem down into a smaller, simpler version of itself, until it reaches a point where the answer is so simple it can be stated directly.

Every recursive function is built from two essential parts:

  1. The Base Case: This is the simplest possible version of the problem, where the answer is known without further calculation. The base case acts as the "emergency brake" that stops the recursion.
  2. The Recursive Step: This is where the function calls itself, but with a modified input that brings it one step closer to the base case. It defines the solution to a problem in terms of the solution to a smaller version of the same problem.

A First Example: Factorial

The factorial function is a classic example. Its mathematical definition is naturally recursive:

  • Base Case: 0! = 1
  • Recursive Step: n! = n * (n - 1)! for n > 0

We can translate this directly into a Python function:

def factorial(n: int) -> int:
    """Calculates the factorial of a non-negative integer using recursion."""
    # Base Case: The simplest problem we can solve directly.
    if n == 0:
        return 1
    # Recursive Step: Solve a bigger problem using the solution to a smaller one.
    else:
        return n * factorial(n - 1)

print(factorial(5)) # Output: 120

Tool Tip: Enabling Type Checking in VS Code

You can get your editor to check these types for you and highlight potential errors before you even run your code! This is one of the biggest benefits of using type hints.

To enable basic type checking in Visual Studio Code:

  1. Open the Command Palette (Ctrl+Shift+P or Cmd+Shift+P on Mac).

  2. Search for and select "Preferences: Open User Settings (JSON)".

  3. Add the following line to your settings.json file:

    "python.analysis.typeCheckingMode": "basic"

Now, VS Code will underline code where the types don't match, such as if you tried to call factorial("hello"). This immediate feedback is a powerful tool for writing correct code.

Recursion on Data Structures

Recursion is even more powerful when applied to data structures like sequences. Let's write a function to sum all the numbers in a tuple. We can define the problem recursively:

  • Base Case: The sum of an empty tuple is 0.
  • Recursive Step: The sum of a non-empty tuple is its first element (the "head") plus the sum of the rest of the elements (the "tail").

Declarative Deconstruction with match

To implement this, we need a way to deconstruct a tuple into its head and tail. While we could use manual slicing (head = t[0], tail = t[1:]), Python's match statement (from Chapter 1) provides a much more declarative way to do this. It lets us describe the structure of the data we're interested in.

from typing import Tuple

def sum_tuple(numbers: Tuple[int, ...]) -> int:
    """Calculates the sum of numbers in a tuple using recursion and pattern matching."""
    match numbers:
        # Base Case: Matches an empty tuple.
        case ():
            return 0
        # Recursive Step: Matches a tuple with a head and a tail.
        # The `*tail` syntax captures all remaining elements into a list.
        case (head, *tail):
            # We call the function again on the smaller tail part.
            # `tail` is a list, so we convert it back to a tuple.
            return head + sum_tuple(tuple(tail))

my_numbers = (1, 2, 3, 4, 5)
print(sum_tuple(my_numbers)) # Output: 15
print(sum_tuple(()))         # Output: 0

This pattern - a base case for an empty structure and a recursive step that processes the head and recurses on the tail - is the fundamental building block for nearly all declarative data processing.

Understanding the Type Hint: Tuple[int, ...]

  • Tuple: This tells the type checker that we are expecting a Python tuple. We import it from the typing module.
  • [...]: The square brackets are used to specify what's inside the tuple.
  • int: This indicates that the elements inside the tuple should be integers.
  • ,: The comma separates the types of the elements.
  • ...: This is a special symbol called an ellipsis. In this context, it means "and then any number of more elements of the same type."

So, Tuple[int, ...] reads as: "a tuple containing an indeterminate number of integers."

This is different from a hint like Tuple[int, str, bool], which means "a tuple containing exactly three elements: an integer, then a string, and finally a boolean." For functions that process sequences of any length, the ellipsis is the tool we need.

Exercise: Product of a Tuple

  • Write a recursive function product_tuple(numbers: Tuple[int, ...]) -> int that calculates the product of all numbers in a tuple.
  • Use a match statement.
  • Think carefully: what should the base case be for multiplication?

2. The Accumulator Pattern

Our first recursive functions, like factorial, work by building up a chain of operations that are only resolved at the very end. When you call factorial(5), the calculation looks like this:

factorial(5)
 -> 5 * factorial(4)
 -> 5 * (4 * factorial(3))
 -> 5 * (4 * (3 * factorial(2)))
 -> 5 * (4 * (3 * (2 * factorial(1))))
 -> 5 * (4 * (3 * (2 * (1 * factorial(0)))))
 -> 5 * (4 * (3 * (2 * (1 * 1))))
 -> ... (and now the multiplications can finally happen)

Notice how the multiplication (*) happens after the recursive call returns. This means the computer has to keep track of all those pending operations, which can use up a lot of memory on the "call stack." For very deep recursion (e.g., factorial(3000)), this can cause a "stack overflow" error.

The accumulator pattern is a technique for rewriting recursion to avoid this problem. The core idea is to pass an extra argument to the function - the accumulator - which holds the intermediate result of the computation at each step.

Rewriting Factorial with an Accumulator

Instead of calculating 5 * 4 * 3 * 2 * 1, we'll calculate ((((1 * 5) * 4) * 3) * 2) * 1. The result is the same, but we can compute it step-by-step without building up pending operations.

def factorial_acc(n: int, accumulator: int = 1) -> int:
    """
    Calculates factorial using the accumulator pattern.
    The accumulator holds the product calculated so far.
    """
    # Base Case: When n is 0, the calculation is done.
    # The final answer is the value in the accumulator.
    if n == 0:
        return accumulator
    # Recursive Step: Call the function with the smaller problem (n-1),
    # but update the accumulator with the result of this step's work.
    else:
        return factorial_acc(n - 1, accumulator * n)

print(factorial_acc(5)) # Output: 120

Let's trace factorial_acc(3, 1) to see how it works:

  1. factorial_acc(3, 1) -> calls factorial_acc(2, 1 * 3)
  2. factorial_acc(2, 3) -> calls factorial_acc(1, 3 * 2)
  3. factorial_acc(1, 6) -> calls factorial_acc(0, 6 * 1)
  4. factorial_acc(0, 6) -> n is 0, so it hits the base case and returns the final accumulator value: 6.

The work is done on the way "down" into the recursion, not on the way "back up." This form of recursion is often called tail recursion because the recursive call is the very last thing the function does.

The Connection to Iteration

The accumulator pattern might look familiar. Let's compare the state of the variables (n and accumulator) in our recursive function to the state of variables in a standard for loop.

Recursive Call Iterative Loop (for n in range(5, 0, -1))
factorial_acc(5, 1) n=5, acc=1
factorial_acc(4, 5) n=4, acc=5
factorial_acc(3, 20) n=3, acc=20
factorial_acc(2, 60) n=2, acc=60
factorial_acc(1, 120) n=1, acc=120
factorial_acc(0, 120) -> returns 120 Loop finishes, returns 120

They are conceptually identical. The accumulator pattern is the declarative way to think about the state that is managed by an imperative loop.

A Note on Python's Implementation

While the accumulator pattern is a crucial concept, it's important to know that Python does not optimize for tail recursion. This means that even a tail-recursive function like factorial_acc will still consume stack space and can cause a stack overflow for very large n.

So why learn it? Because it's a fundamental pattern in declarative and functional programming. It teaches you to think about state in a disciplined, stateless way. In practical Python, if you see a problem that fits the accumulator pattern, the most direct and efficient implementation is usually a simple for or while loop.

Exercise: Reversing a Tuple

  • Write a recursive function reverse_tuple(a_tuple: Tuple, acc: Tuple = ()) -> Tuple that reverses a tuple.
  • Use the accumulator pattern. The accumulator should build up the reversed tuple.
  • Use the match statement to deconstruct a_tuple.
  • For example, reverse_tuple((1, 2, 3)) should return (3, 2, 1).
Hint

In each recursive step, you will take the head of the input tuple and prepend it to the acc tuple. The new accumulator will be (head,) + acc.

3. Abstracting Control Flow

So far, we have used recursion and iteration to control the flow of our programs. We've treated control flow constructs like if, while, and recursive calls as fixed parts of the language syntax.

In this section, we will take a significant step towards a more powerful, declarative style. We will learn to see control flow not as rigid syntax, but as a reusable pattern that can be abstracted. Just as we can pass data like numbers or tuples into a function, we can also pass in the logic of a loop itself. This is a powerful idea made possible by higher-order functions - functions that can take other functions as arguments.

A Common Pattern: Iterative Processes

Let's look at a simple iterative process, Newton's method for finding the square root of a number. You don't need to understand the math in detail; just focus on the structure of the code. The algorithm starts with a guess and repeatedly improves it until it's "good enough."

def sqrt_newton(x: float) -> float:
    # 1. Define the initial state
    guess = 1.0

    # 2. Define the "done" condition
    def is_good_enough(g):
        return abs(g * g - x) < 0.00001

    # 3. Define the state transformation
    def improve_guess(g):
        return (g + x / g) / 2.0

    # The control flow loop
    while not is_good_enough(guess):
        guess = improve_guess(guess)

    # 4. Return the final state
    return guess

print(sqrt_newton(25)) # Output: 5.000000000053722

This process has a clear, generic structure:

  1. It starts with an initial state (guess).
  2. It loops as long as a "done" condition is false.
  3. In each step, it applies a transformation to get the next state.
  4. It returns the final state.

This pattern appears everywhere, not just in mathematical algorithms.

Building a Generic Control Abstraction

What if we could write the while loop just once and reuse it for any iterative process? We can do this by creating a higher-order function that takes the specific logic of the process as arguments.

Let's build a function called iterate that encapsulates this pattern.

from typing import TypeVar, Callable

# A generic type variable for the state
State = TypeVar('State')

def iterate(
    initial_state: State,
    is_done_func: Callable[[State], bool],
    transform_func: Callable[[State], State]
) -> State:
    """A generic control abstraction for any iterative process."""
    state = initial_state
    # The while loop is now hidden inside this reusable function
    while not is_done_func(state):
        state = transform_func(state)
    return state

A Note on Type Hinting:

  • TypeVar('State') creates a generic type variable. This lets us tell the type checker that initial_state, the argument to the functions, and the return value all have the same, unspecified type.
  • Callable[[State], bool] is a hint for a function that takes one argument of type State and returns a bool.

Using the Abstraction

Now, we can re-implement our square root function in a purely declarative way. We no longer write the while loop; we simply describe the three components of the process and pass them to our iterate function.

def sqrt_declarative(x: float) -> float:
    # We describe the "what", not the "how".
    # The mechanics of the loop are handled by 'iterate'.
    initial = 1.0
    is_done = lambda g: abs(g * g - x) < 0.00001
    transform = lambda g: (g + x / g) / 2.0

    return iterate(initial, is_done, transform)

print(sqrt_declarative(25)) # Output: 5.000000000053722

This is a profound shift in thinking. We've taken a fundamental piece of control flow - the while loop - and turned it into an abstraction. This allows us to focus on the logic of our problem (the three functions) and separate it from the mechanics of iteration. This separation of concerns is a core tenet of good declarative programming.

Exercise: Summing Numbers

  • Use the iterate function to calculate the sum of numbers from 1 to N (e.g., 1+2+3+...+N).
  • To do this, you'll need to define a state that keeps track of two things: the current number being added and the sum so far. A good state representation would be a tuple: (current_num, current_sum).
  • Define the initial_state, is_done_func, and transform_func needed to solve this problem.
Hint
  • initial_state: (1, 0) (Start with number 1, sum is 0)
  • is_done_func: The loop is done when current_num is greater than N. Your lambda will be lambda state: state[0] > N.
  • transform_func: This should return the next state tuple. If the current state is (i, s), the next state should be (i + 1, s + i).
  • The final result will be the current_sum part of the final state tuple.

Topic 2: Immutable Data

4. The Principle of Immutability

In declarative programming, we've focused on functions that are pure and predictable. This predictability relies on the assumption: the data objects our functions operate on cannot be changed in unexpected ways. This leads to an important concept in Python's data model: mutability.

Variables vs. Objects: A Quick Clarification

It's important to distinguish between a variable (a name) and an object (the data value).

  • A variable is a label. In Python, you can always re-assign this label to point to a different object (x = 10, then x = 20).
  • An object is the actual data in memory. Mutability is a property of the object itself. Can this object be changed in-place?

Data types that cannot be changed in-place are called immutable. Data types that can be modified are mutable.

Immutable Types (Value cannot change in-place) Mutable Types (Value can change in-place)
int, float, bool list
str dict
tuple set
frozenset Most custom class objects

When you perform an operation like x = x + 1, you are not changing the number 10. You are creating a new number object, 11, and re-assigning the label x to it. In contrast, my_list.append(4) modifies the original list object directly.

For declarative programming, using immutable types is a fundamental discipline. It provides a guarantee that no function can secretly change the data it receives. This eliminates a huge category of bugs and makes our programs safe and predictable. Our core principle will be: instead of changing data, we create new data.

A Cautionary Tale: The Danger of Hidden State

To understand why this discipline is so important, let's look at a classic Python pitfall where a seemingly harmless function hides a dangerous piece of mutable state.

Consider a function designed to add an item to a list.

from typing import List, Any

# A function that looks declarative, but has a hidden stateful bug
def add_item_buggy(item: Any, target_list: List[Any] = []) -> List[Any]:
    """Appends an item to a list. Uses a mutable default argument."""
    target_list.append(item)
    return target_list

This function looks simple enough. Let's see what happens when we call it.

# First call
list1 = add_item_buggy("a")
print(f"List 1: {list1}")

# Second call, expecting a new list with just "b"
list2 = add_item_buggy("b")
print(f"List 2: {list2}")

# Let's check the first list again
print(f"List 1 is now: {list1}")

Output:

List 1: ['a']
List 2: ['a', 'b']
List 1 is now: ['a', 'b']

This is a disaster! The second call didn't create a new list; it modified the same list used by the first call. Why?

The default argument [] is created only once, when the function is first defined. It becomes a single, shared, mutable object that persists across all calls to add_item_buggy that don't provide a target_list. This hidden shared state completely breaks the declarative promise of predictability.

The Declarative Solution: Use Immutable Data

The correct way to handle this in a declarative style is to use immutable data structures and to never modify inputs. The standard Python tuple is our primary tool for this.

Let's fix the problem by creating a "safe" version that operates on tuples.

from typing import Tuple, Any

def add_item_safe(item: Any, target_tuple: Tuple[Any, ...] = ()) -> Tuple[Any, ...]:
    """Appends an item to a tuple by creating and returning a new tuple."""
    # We don't modify the original tuple. We create a new one.
    return target_tuple + (item,)

# First call
tuple1 = add_item_safe("a")
print(f"Tuple 1: {tuple1}")

# Second call. This cannot affect tuple1.
tuple2 = add_item_safe("b")
print(f"Tuple 2: {tuple2}")

# The first tuple remains unchanged, as expected.
print(f"Tuple 1 is still: {tuple1}")

Output:

Tuple 1: ('a',)
Tuple 2: ('b',)
Tuple 1 is still: ('a',)

This version is predictable and safe. Each call creates a completely new tuple, preserving the integrity of the original data. This is the discipline we will follow: instead of changing data, we create new data.

Exercise 1: Fixing the Mutable Default

The "buggy" function add_item_buggy can be fixed while still using a list by handling the default argument correctly. The standard Python idiom is to use None as the default and create a new list inside the function if one isn't provided.

  • Create a function add_item_fixed(item, target_list=None) that implements this logic.
  • Verify that it no longer shares state between calls and behaves predictably.
Hint

The first line inside your function should be if target_list is None: target_list = [].

Exercise 2: Declarative Update

Imagine you are storing user records as simple tuples: (user_id, name, email). Because tuples are immutable, you cannot change a user's email directly.

  • Write a function update_email(user_record: tuple, new_email: str) -> tuple.
  • This function should take a user record tuple and a new email address.
  • It must return a new tuple representing the updated record, without modifying the original.

For example:

user1 = (101, "Alice", "alice@old.com")
user2 = update_email(user1, "alice@new.com")

print(user1)  # Expected: (101, 'Alice', 'alice@old.com')
print(user2)  # Expected: (101, 'Alice', 'alice@new.com')

5. Processing Immutable Data

Now that we have established the principle of immutability, we need patterns for working with these unchangeable data structures. If we can't modify data, how do we perform operations that seem to require modification, like adding an element or updating a value?

The answer is always the same: we create a new data structure that contains the result of the operation. This is typically done with our foundational tool: recursion.

Processing Immutable Sequences with Recursion

Let's write a function that takes a tuple of numbers and returns a new tuple where every number has been doubled. We'll use the recursive match pattern we learned in Section 1.

from typing import Tuple

def double_all(numbers: Tuple[int, ...]) -> Tuple[int, ...]:
    """
    Recursively processes a tuple, returning a new tuple with all elements doubled.
    """
    match numbers:
        # Base Case: Doubling an empty tuple results in an empty tuple.
        case ():
            return ()
        # Recursive Step:
        case (head, *tail):
            return (head * 2,) + double_all(tuple(tail))

original = (1, 2, 3, 4)
doubled = double_all(original)

print(f"Original: {original}") # Output: Original: (1, 2, 3, 4)
print(f"Doubled:  {doubled}")  # Output: Doubled:  (2, 4, 6, 8)

This function perfectly embodies the declarative style. It takes a value (original) and produces a new value (doubled) without causing any side effects. The original tuple is completely untouched and can be safely used elsewhere.

Processing Immutable Trees

This pattern of creating new data extends naturally to more complex structures like trees. To work with immutable trees, we first need a way to define them. Python's dataclasses are an excellent modern tool for this, especially with the frozen=True option, which makes instances of the class immutable.

from dataclasses import dataclass
from typing import Union

# An immutable tree node definition
@dataclass(frozen=True)
class Node:
    value: int
    left: 'Tree'
    right: 'Tree'

# A type alias to define what a Tree can be
Tree = Union[Node, None]

A Look at the Tools:

  • @dataclass(frozen=True): This decorator automatically generates methods like __init__ and __repr__ for us, making the class easy to create and print. The frozen=True argument is crucial: it makes instances of Node immutable. If you try to change a value (e.g., my_node.value = 10), Python will raise an error.
  • Why is 'Tree' in quotes? This is called a forward reference. Notice that inside the Node class, we are referring to the name Tree. However, Tree is only defined after the Node class is finished.
  • Union[Node, None]: This type hint, which we name Tree, tells our type checker that a variable annotated as Tree can hold either a Node object or the value None. In our model, None represents a leaf or an empty branch, which serves as the base case for our recursion.

Now, let's build a simple, immutable tree using our Node class.

# Let's build a simple, immutable tree.
#       10
#      /  \
#     5    15
#         /
#        12
my_tree: Tree = Node(10,
    Node(5, None, None),
    Node(15, Node(12, None, None), None)
)

Now, let's write a function increment_tree(tree) that returns a new tree where the value of every node has been increased by one.

def increment_tree(tree: Tree) -> Tree:
    """
    Recursively traverses an immutable tree, returning a new tree
    with all node values incremented.
    """
    # Base Case: An empty branch (leaf) remains empty.
    if tree is None:
        return None
    # Recursive Step:
    else:
        # 1. Recursively build the new left and right subtrees.
        new_left = increment_tree(tree.left)
        new_right = increment_tree(tree.right)
        # 2. Create a new Node with the incremented value and the new subtrees.
        return Node(tree.value + 1, new_left, new_right)

incremented_tree = increment_tree(my_tree)

print(f"Original tree: {my_tree}")
# Node(value=10, left=Node(value=5, left=None, right=None), right=Node(value=15, left=Node(value=12, left=None, right=None), right=None))
print(f"Incremented tree: {incremented_tree}")
# Node(value=11, left=Node(value=6, left=None, right=None), right=Node(value=16, left=Node(value=13, left=None, right=None), right=None))

The logic is the same as with the tuple: we deconstruct the data, recursively process its smaller parts, and then construct a new piece of data from the results. The original my_tree is completely unaffected.

Exercise: Filtering a Tuple

  • Write a recursive function filter_odds(numbers: Tuple[int, ...]) -> Tuple[int, ...].
  • This function should take a tuple of integers and return a new tuple containing only the odd numbers from the original.
  • Use the match statement.
Hint

Your recursive step will have two paths based on whether head is odd or even.

  • If head is odd: Combine the head with the result of filtering the tail.
  • If head is even: Ignore the head and simply return the result of filtering the tail.

A Note on a More Pythonic Way

If you have experience with Python, you might have realized there's a much more concise way to solve the filter_odds exercise, perhaps with a single line of code.

Python has powerful, built-in tools like comprehensions and generator expressions that abstract away the manual recursion we've been writing.

For now, the goal of this section was to master the fundamental, manual pattern of recursive data processing. Understanding how to build these functions from scratch is essential for grasping the declarative model. In the very next topic, we will explore these more powerful, higher-order abstractions that let us automate these patterns and write even more elegant declarative code.

Topic 3: Higher-Order Abstractions

6. Functions as Arguments

In the previous sections, we wrote recursive functions to process immutable data. Let's look at two functions: one to double all numbers in a tuple, and one to convert all strings in a tuple to uppercase.

from typing import Tuple

def double_all(numbers: Tuple[int, ...]) -> Tuple[int, ...]:
    match numbers:
        case ():
            return ()
        case (head, *tail):
            # The specific logic is here:
            processed_head = head * 2
            return (processed_head,) + double_all(tuple(tail))

def uppercase_all(words: Tuple[str, ...]) -> Tuple[str, ...]:
    match words:
        case ():
            return ()
        case (head, *tail):
            # The specific logic is here:
            processed_head = head.upper()
            return (processed_head,) + uppercase_all(tuple(tail))

Look closely at the structure of these two functions. They are almost identical. Both have a base case for an empty tuple and a recursive step that deconstructs the tuple, processes the head, recurses on the tail, and combines the results. The only part that's different is the single line of logic that processes the head.

This kind of repetition is a sign that we have an opportunity to abstract the pattern. What if we could write the recursive "scaffolding" just once, and then simply "plug in" the specific operation we want to perform?

Higher-Order Functions

We can achieve this with a higher-order function - a function that either takes another function as an argument, returns a function, or both. For now, we'll focus on the first kind.

Let's create a generic function, my_map, that abstracts the recursive pattern of applying an operation to every element of a sequence. It will take two arguments: the tuple to process and the function to apply to each element.

from typing import Tuple, Callable, TypeVar

# Generic type variables for input and output types
In = TypeVar('In')
Out = TypeVar('Out')

def my_map(
    a_tuple: Tuple[In, ...],
    func: Callable[[In], Out]
) -> Tuple[Out, ...]:
    """
    A generic recursive map. Applies a function to every element of a tuple.
    """
    match a_tuple:
        case ():
            return ()
        case (head, *tail):
            # Apply the passed-in function to the head
            processed_head = func(head)
            # Recurse on the tail and combine
            return (processed_head,) + my_map(tuple(tail), func)

A Look at the Type Hint: Callable[[In], Out] describes a function (a "callable") that takes one argument of type In and returns a value of type Out.

Using Our Abstraction

With my_map, our previous functions become trivial, one-line declarations. We no longer need to write the recursion ourselves; we just provide the specific operation.

For simple, one-off operations, we don't even need to define a named function. We can use a lambda to create a small, anonymous function on the fly.

numbers = (1, 10, 20)
words = ("hello", "world")

# Re-implementing double_all using my_map
doubled = my_map(numbers, lambda n: n * 2)
print(doubled)  # Output: (2, 20, 40)

# Re-implementing uppercase_all using my_map
uppercased = my_map(words, lambda s: s.upper())
print(uppercased) # Output: ('HELLO', 'WORLD')

# We can now do any mapping operation easily
is_even = my_map(numbers, lambda n: n % 2 == 0)
print(is_even)  # Output: (False, True, True)

We have successfully separated the general logic of traversing a sequence from the specific logic of what to do with each element. This makes our code more reusable, less repetitive, and easier to read, as the intent is much clearer.

Manually writing functions like my_map is a great way to understand the concept. As we'll see in the next section, Python provides even more direct and powerful syntax for these common declarative patterns.

Exercise: Build Your Own filter

  • Following the pattern of my_map, write a higher-order function my_filter(a_tuple, predicate_func).
  • The predicate_func will be a function that takes one element and returns True or False.
  • my_filter should return a new tuple containing only the elements for which the predicate function returns True.
Hint

The structure will be very similar to my_map. In the recursive step, you will need an if statement. If predicate_func(head) is true, you combine the head with the recursive result. If it's false, you discard the head and just return the recursive result.

7. Comprehensions and Generators

In the last section, we learned how to abstract recursive patterns like mapping and filtering into our own higher-order functions.

Python has a direct, highly readable, and powerful syntax for these exact operations: comprehensions. A comprehension is a concise, declarative way to create a new sequence by describing its contents.

List Comprehensions: The Eager Approach

Let's revisit our goal of doubling every number in a sequence. Instead of calling a my_map function, we can use a list comprehension. It reads almost like plain English.

numbers = (1, 2, 3, 4, 5)

# "Create a new list containing n*2 for each n in numbers"
squares = [n * 2 for n in numbers]

print(squares) # Output: [1, 4, 9, 16, 25]

The syntax [expression for item in iterable] is a direct, declarative statement about the final list. This is the preferred, "Pythonic" way to perform map operations.

We can easily add a filtering condition. This combines the patterns of map and filter into one elegant expression.

numbers = (1, 2, 3, 4, 5, 6)

# "Create a list of n*n for each n in numbers, IF n is even"
even_squares = [n * n for n in numbers if n % 2 == 0]

print(even_squares) # Output: [4, 16, 36]

With one line, we have specified what we want - the squares of even numbers - without managing recursion, append calls, or explicit if blocks. This is the essence of declarative style in Python.

Generator Expressions: The Lazy Approach

List comprehensions are great, but they are eager: they compute the entire new list and store it in memory all at once. This can be inefficient if the input sequence is very large or even infinite (like the streams we'll see later).

A generator expression provides a lazy alternative. It uses the same syntax as a list comprehension, but with parentheses () instead of square brackets [].

Instead of building a list, it creates a generator object - an iterable that produces the values one by one, only when you ask for them.

numbers = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)

# Note the parentheses ()
lazy_even_squares = (n * n for n in numbers if n % 2 == 0)

# At this point, no calculation has been done.
# We have only created a "recipe" for the values.
print(lazy_even_squares) # Output: <generator object <genexpr> at 0x...>

# The generator only computes a value when we ask for it with next().
print(next(lazy_even_squares)) # Computes and returns 4
print(next(lazy_even_squares)) # Computes and returns 16

# We can also use it in a for loop, which calls next() automatically.
for square in lazy_even_squares:
    print(square) # Computes and returns 36, 64, ...

Generator expressions are the most memory-efficient tool for declarative data processing in Python. They allow us to define complex transformations on data streams without ever needing to store the intermediate results in memory.

Checkpoint: Choosing the Right Tool

You have now seen three ways to process sequences declaratively:

  1. Manual Recursion (my_map, my_filter): Excellent for understanding the underlying model, but verbose for practical use.
  2. List/Tuple Comprehension: Eagerly computes and stores the entire result. Best for smaller, finite sequences where you need the full result at once.
  3. Generator Expression: Lazily computes each value on demand. Best for large or potentially infinite sequences to save memory.

For most day-to-day declarative tasks, comprehensions and generator expressions are the go-to tools in Python.

Exercise: Data Cleanup

You are given a list of dictionaries, each representing a user. Some users are missing the 'email' key, and some have an empty email string.

users = [
    {"name": "Alice", "email": "alice@example.com"},
    {"name": "Bob"},
    {"name": "Charlie", "email": ""},
    {"name": "David", "email": "david@example.com"},
]
  • Using a single list comprehension, create a new list containing only the valid email addresses. An email is valid if the 'email' key exists and its value is not an empty string.
  • The final list should be ['alice@example.com', 'david@example.com'].
Hint

You can check for key existence with 'email' in u and for a non-empty string with u['email'].

8. Building Lazy Pipelines

The true power of generators and lazy evaluation becomes apparent when we chain them together. We can create a multi-stage data processing pipeline where each stage is a simple, declarative generator that performs one specific task. Data flows through this pipeline one element at a time, on demand, resulting in incredibly memory-efficient code.

This pattern is the foundation of stream processing in many programming languages and is a cornerstone of advanced declarative and functional programming.

A Simple Pipeline

Let's imagine we have a stream of sensor data and we want to perform a series of operations:

  1. Filter out any negative (invalid) readings.
  2. Calibrate the valid readings by doubling them.
  3. Convert the calibrated readings into formatted strings.

Instead of performing each step on an entire list, we can build a lazy pipeline.

# Our source data stream (could be a file, a network socket, etc.)
# For this example, it's a simple tuple.
sensor_readings = (3, 5, -1, 10, -2, 8)

# Stage 1: Filter out invalid readings.
# This generator yields only positive numbers.
valid_readings = (r for r in sensor_readings if r > 0)

# Stage 2: Calibrate the data.
# This generator takes its input from the previous stage.
calibrated_readings = (r * 2 for r in valid_readings)

# Stage 3: Format the results.
# This generator takes its input from the calibration stage.
formatted_output = (f"Reading: {r}" for r in calibrated_readings)

At this point, no actual work has been done. We have simply constructed a pipeline of generator objects, each one ready to pull data from the one before it. The computation only happens when we request data from the end of the pipeline.

# Pulling one value causes it to flow through the entire pipeline:
# 3 -> valid -> 3 -> calibrated -> 6 -> formatted -> "Reading: 6"
print(next(formatted_output)) # Output: Reading: 6

# Pulling the next value:
# 5 -> valid -> 5 -> calibrated -> 10 -> formatted -> "Reading: 10"
print(next(formatted_output)) # Output: Reading: 10

# The invalid reading (-1) is dropped by the first stage and never reaches the others.

We can consume the rest of the stream with a for loop:

for item in formatted_output:
    print(item)

Output:

Reading: 20
Reading: 16

Pipelines with Infinite Data

Because no intermediate lists are ever created, this technique works perfectly even with infinite data streams. Let's build a pipeline to find the first 5 numbers that are multiples of 3, squared.

from itertools import count, islice

# Stage 1: An infinite stream of integers starting from 1.
# `itertools.count(1)` is a built-in, efficient integer generator.
all_integers = count(1)

# Stage 2: Filter for multiples of 3.
multiples_of_3 = (i for i in all_integers if i % 3 == 0)

# Stage 3: Square the results.
squared_multiples = (x * x for x in multiples_of_3)

# Stage 4: Take just the first 5 results from our infinite stream.
# `itertools.islice` is a lazy way to get a slice of any iterable.
first_five_results = islice(squared_multiples, 5)

# Now, consume the final result. The pipeline will only do enough
# work to generate these 5 values.
print(list(first_five_results)) # Output: [9, 36, 81, 144, 225]

The all_integers generator could have run forever, but because each stage in the pipeline is lazy, it only did exactly enough work to satisfy the final request for 5 items. This is the ultimate expression of declarative efficiency: we describe an entire, potentially infinite process, and the system intelligently executes only the bare minimum required to produce the result we ask for.

Exercise: Prime Number Pipeline

  • You will build a pipeline to find the sum of the first 100 prime numbers.
  • You are given a simple (but not very efficient) function to check for primality: 
    def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True
  • Your task:
    1. Create an infinite stream of integers starting from 2.
    2. Create a generator that filters this stream, yielding only the prime numbers.
    3. Create a generator that takes the first 100 values from your prime number stream.
    4. Use the built-in sum() function on your final generator to get the answer (24133).
Hint

Your pipeline will look very similar to the "infinite data" example above. You'll use itertools.count(), a generator expression with the is_prime() function in its if clause, and itertools.islice().

Topic 4: Encapsulated Components

9. Declarative Abstract Data Types

We have learned to think recursively, work with immutable data, and abstract patterns with higher-order functions. Now, we will combine all these ideas to build robust, reusable, and purely declarative components.

The primary tool for this is the Abstract Data Type (ADT). An ADT is a formal description of a data structure that is defined by its interface - the set of operations it supports - not by its underlying implementation. This creates a clean separation between what the component does and how it does it.

In a declarative context, an ADT has one crucial rule: all of its operations must be pure functions. This means that operations that "modify" the ADT do not change the original instance; instead, they return a new instance representing the changed state.

The Declarative Stack

Let's define and implement a classic Stack as a declarative ADT.

1. The Interface A stack should support the following operations:

  • create(): Create a new, empty stack.
  • push(item): Add an item to the top of the stack, returning a new stack.
  • pop(): Remove the top item, returning the item and a new stack.
  • is_empty(): Check if the stack is empty.

2. The Implementation We will implement this interface using Python's @dataclass(frozen=True). This is the perfect tool for creating a simple, immutable object. The underlying data will be stored in an immutable tuple.

from dataclasses import dataclass
from typing import Tuple, Any

@dataclass(frozen=True)
class DeclarativeStack:
    """A purely declarative, immutable Stack ADT."""
    # The internal state is an immutable tuple.
    _items: Tuple[Any, ...] = ()

    def push(self, item: Any) -> 'DeclarativeStack':
        """Returns a new stack with the item added."""
        # This does not modify `self`. It creates a new instance.
        return DeclarativeStack(self._items + (item,))

    def pop(self) -> Tuple[Any, 'DeclarativeStack']:
        """Returns the top item and a new stack without that item."""
        if self.is_empty():
            raise IndexError("pop from empty stack")
        
        top_item = self._items[-1]
        remaining_items = self._items[:-1]
        # Return the value and the new, smaller stack instance.
        return (top_item, DeclarativeStack(remaining_items))

    def is_empty(self) -> bool:
        """Checks if the stack is empty."""
        return not self._items

A Note on Self: The Self type hint (available in Python 3.11+) is a precise way to say "an instance of this same class." For older Python versions, you would use a quoted string of the class name, like 'DeclarativeStack'.

Using the Declarative Stack

Let's see our immutable ADT in action. Notice how every operation that changes the stack gives us back a new object, leaving the original untouched. This creates a "history" of the stack's states that we can refer back to at any time.

# s0 represents the initial empty state.
s0 = DeclarativeStack()
print(f"s0 is empty: {s0.is_empty()}")

# Pushing "a" creates a new stack, s1. s0 is unchanged.
s1 = s0.push("a")
print(f"s1: {s1}")
print(f"s0 is still empty: {s0.is_empty()}")

# Pushing "b" onto s1 creates s2.
s2 = s1.push("b")
print(f"s2: {s2}")

# Popping from s2 gives us the value "b" and a new stack, s3.
# s3 should be identical to s1.
value, s3 = s2.pop()
print(f"Popped value: {value}")
print(f"s3 is the same as s1: {s3 == s1}")

# s2 remains unchanged by the pop operation.
print(f"s2 still exists: {s2}")

Output:

s0 is empty: True
s1: DeclarativeStack(_items=('a',))
s0 is still empty: True
s2: DeclarativeStack(_items=('a', 'b')) 
Popped value: b
s3 is the same as s1: True
s2 still exists: DeclarativeStack(_items=('a', 'b'))

We have created a fully encapsulated, predictable, and safe data structure. Its immutability guarantees that it will have no side effects, making it a perfect "LEGO brick" for building larger, more complex declarative programs.

Exercise: Declarative Queue

  • Implement a DeclarativeQueue ADT using a @dataclass(frozen=True) and a tuple.
  • A queue has FIFO (First-In, First-Out) behavior.
  • It should have the following methods:
    • enqueue(item): Adds an item to the back of the queue, returning a new queue.
    • dequeue(): Removes an item from the front of the queue, returning the item and a new queue.
    • is_empty()
Hint

enqueue will be similar to push: new_items = self._items + (item,). For dequeue, the value you return will be self._items[0] and the new tuple will be self._items[1:].

10. Case Study: A Declarative Key-Value Store

We have now mastered the individual techniques of declarative programming. To see how they all come together to solve a practical, non-trivial problem, we will build our own immutable key-value store. This is essentially a declarative version of Python's dictionary.

The Problem: Efficient Lookup

Imagine we wanted to store key-value pairs using only the tools we've used so far. A simple approach would be to use a tuple of tuples: (('name', 'Alice'), ('id', 101)).

How would we find the value for the key 'id'? We would have to scan the tuple from the beginning until we found a matching key. For a collection with n items, this would take, on average, n/2 steps. This is known as O(n) or linear time complexity. For a million items, this means a million operations - far too slow.

We need a smarter data structure. A Binary Search Tree (BST) is a perfect fit. By keeping its elements ordered, it allows us to find any item in roughly O(log n) or logarithmic time. For a million items, this is only about 20 operations - a massive improvement.

The Data Structure: An Immutable BST

A Binary Search Tree is a tree where every node has a key, and it follows a simple rule:

For any given node, all keys in its left subtree are smaller than its own key, and all keys in its right subtree are larger.

We can represent this using the same immutable Node pattern we saw earlier.

from dataclasses import dataclass
from typing import Any, Union, Generic, TypeVar

# Generic type variables for keys and values
K = TypeVar('K')
V = TypeVar('V')

@dataclass(frozen=True)
class Node(Generic[K, V]):
    key: K
    value: V
    left: 'Tree[K, V]'
    right: 'Tree[K, V]'

Tree = Union[Node[K, V], None]

A Look at Generics: TypeVar and Generic

TypeVar and Generic are Python's tools for creating generic types - components that can work with many different kinds of data. Our DeclarativeMap should be able to store keys and values of any type (integers, strings, etc.), as long as the keys can be ordered. Generics let us express this.

  • K = TypeVar('K'): This creates a generic "type variable" named K. Think of it as a placeholder for a type that will be specified later. We use K by convention for "Key."
  • V = TypeVar('V'): This creates a second type variable for the "Value."
  • class Node(Generic[K, V]):: By inheriting from Generic[K, V], we are telling the type checker that our Node class is generic. It depends on two types, K and V, which will be used inside the class.
  • key: K and value: V: Inside the class, we use K and V just like regular types. This declares that whatever type is eventually used for K will be the type of the key attribute.
  • Tree[K, V]: When we use our generic Node or Tree alias, we can specify the concrete types. For example, a variable annotation like my_tree: Tree[str, int] would declare a tree that maps string keys to integer values.

The Core Operations: Declarative and Recursive

Now, let's implement the core operations. All of these will be pure, recursive functions.

1. Looking Up a Value

Looking up a key is a straightforward recursive traversal. At each node, we decide whether to go left, right, or stop.

def lookup(tree: Tree[K, V], key: K) -> V:
    """Recursively searches for a key in the tree and returns its value."""
    if tree is None:
        raise KeyError(f"Key not found: {key}")
    
    if key == tree.key:
        return tree.value
    elif key < tree.key:
        return lookup(tree.left, key)
    else: # key > tree.key
        return lookup(tree.right, key)

2. Inserting a Value

This is the most important operation for understanding declarative data modification. The insert function does not change the tree. Instead, it returns a brand new tree that includes the new node.

It works by recursively rebuilding the path from the root down to where the new node belongs. Any subtrees that are not on this path are "shared" by simply reusing the reference, making the operation more efficient than it sounds.

def insert(tree: Tree[K, V], key: K, value: V) -> Node[K, V]:
    """
    Recursively returns a new tree with the key-value pair inserted.
    If the key already exists, it returns a new tree with the value updated.
    """
    # Base Case: We found an empty spot, so we create a new node.
    if tree is None:
        return Node(key, value, None, None)

    # Recursive Step: Go left or right.
    if key < tree.key:
        # Recursively build a new left subtree.
        new_left = insert(tree.left, key, value)
        # Return a new parent node, reusing the old right subtree.
        return Node(tree.key, tree.value, new_left, tree.right)
    elif key > tree.key:
        # Recursively build a new right subtree.
        new_right = insert(tree.right, key, value)
        # Return a new parent node, reusing the old left subtree.
        return Node(tree.key, tree.value, tree.left, new_right)
    else: # key == tree.key
        # The key already exists. Return a new node with the updated value.
        return Node(key, value, tree.left, tree.right)

Putting It All Together: A DeclarativeMap ADT

Finally, we can wrap our recursive functions in a clean, user-friendly ADT. This class will hold the root of the tree and provide a simple interface.

@dataclass(frozen=True)
class DeclarativeMap(Generic[K, V]):
    _root: Tree[K, V] = None

    def put(self, key: K, value: V) -> 'DeclarativeMap[K, V]':
        """Returns a new map with the key-value pair added."""
        new_root = insert(self._root, key, value)
        return DeclarativeMap(new_root)

    def get(self, key: K) -> V:
        """Returns the value for a key."""
        return lookup(self._root, key)

# --- Usage Example ---
m0 = DeclarativeMap()
m1 = m0.put("name", "Alice")
m2 = m1.put("id", 101)
m3 = m2.put("city", "New York")
m4 = m3.put("name", "Alicia") # Updates the existing key

print(f"Name in m3: {m3.get('name')}")   # Alice
print(f"Name in m4: {m4.get('name')}")   # Alicia
print(f"City in m4: {m4.get('city')}")   # New York

Exercise: In-Order Traversal

A powerful feature of a BST is that an "in-order" traversal visits all nodes in sorted key order.

  • Write a recursive generator function traverse_in_order(tree: Tree).
  • This function should yield the (key, value) pairs from the tree in ascending order of keys.
  • To perform an in-order traversal:
    1. Recursively traverse the left subtree.
    2. yield the current node's (key, value).
    3. Recursively traverse the right subtree.
Hint

You will need to use yield from to delegate to the recursive calls. The structure will be: yield from traverse_in_order(tree.left), then yield (tree.key, tree.value), then yield from traverse_in_order(tree.right). Don't forget the base case for when the tree is None.

for key, value in traverse_in_order(m4._root):
    print(f"Key: {key}, Value: {value}")

11. Chapter Summary

In this chapter, we took a deep dive into the declarative programming paradigm, a style focused on describing what you want to compute rather than the step-by-step instructions for how to do it. We learned that by building components that are stateless, independent, and deterministic, we can create programs that are easier to reason about, test, and compose.

Let's recap the core concepts and techniques we covered on our journey from basic recursion to a fully-featured declarative component:

  1. Recursion as the Foundation: We established recursion as the primary tool for repetition in the declarative model. We learned to structure functions with a base case and a recursive step, and used the powerful accumulator pattern to write more efficient, iterative-style logic in a declarative way.

  2. Immutability as a Discipline: We established the critical importance of using immutable data. By exclusively using structures like tuples and frozen dataclasses, and by adopting the pattern of creating new data instead of modifying old data, we learned how to eliminate side effects and guarantee predictable behavior.

  3. Abstraction of Patterns: We moved beyond manual recursion by learning to abstract away common patterns.

    • Higher-Order Functions like map and filter allowed us to pass behavior (functions) as arguments, separating the "what" from the "how."
    • Comprehensions and Generator Expressions provided a concise, Pythonic syntax for these declarative transformations, with generators enabling lazy, memory-efficient data pipelines.

  4. A Complete Declarative Component: We synthesized all these techniques in a final case study by building a declarative key-value store using an immutable Binary Search Tree. This demonstrated how to build a non-trivial, efficient data structure (DeclarativeMap) that remains purely declarative, with operations like put returning new instances instead of modifying state.

The Road Ahead

You now have a solid foundation in declarative thinking. You know how to solve complex problems using a pure, functional style. As we move into the next chapter, "State and Object-Oriented Programming," we will begin to relax the strict rule of immutability. We will explore why and when we might need to introduce state, and how the principles of object-oriented programming help us manage the new complexities that arise when our components are allowed to have a memory.