Higher-Order Functions

Practice SICP-style higher-order functions in Python: treat functions as data, reason about closures and composition, and build new behavior by returning and combining functions.

0. Functions as Data (SICP Ex 1.34 in Python)

**Predict the output** before running this code.

This is a Python version of SICP Exercise 1.34.

```python
def f(g):
    return g(2)

def square(x):
    return x * x

h = lambda z: z * (z + 1)

print(f(square))
print(f(h))
print(f(f))
```

1. What are the first two lines that get printed?
2. What happens when we try to evaluate `print(f(f))`?

Choose the best description:

A. Prints `4`, then `6`, then `4` again.

B. Prints `4`, then `6`, then `6` again.

C. Prints `4`, then `6`, then causes a **TypeError** before printing a third line.

D. Causes a **TypeError** on the very first call `f(square)`.

Write down your prediction in a comment, **then** run the code to check.

def f(g):
    return g(2)

def square(x):
    return x * x

h = lambda z: z * (z + 1)

# First, write your prediction as comments:
# 1) I think print(f(square)) will print: ______
# 2) I think print(f(h)) will print: ______
# 3) I think print(f(f)) will: __________________________
#    (pick one: print a number / raise an error / something else?)

# Then uncomment the lines below to check:
#print(f(square))
#print(f(h))
#print(f(f))

Remember: in `def f(g): return g(2)`, the parameter `g` is expected to be **callable**.

`square` and `h` are both functions, so `f(square)` means `square(2)` and `f(h)` means `h(2)`.

For `f(f)`, first substitute: `g` becomes the function `f`. Then think carefully about what happens when `f` is called **inside** `f`.

For the first two calls:

- `f(square)`:
  - `g` is `square`, so `f(square)` computes `square(2)` → `4`.
- `f(h)`:
  - `g` is `h`, so `f(h)` computes `h(2)`.
  - `h(2) = 2 * (2 + 1) = 2 * 3 = 6`.

So the program successfully prints:

```
4
6
```

Now consider `f(f)`:

1. We call `f` with `g = f`. So inside the body of `f`, `g` refers to the function `f`.
2. The body says `return g(2)`, so this becomes `return f(2)`.
3. Now we are calling `f` again, but this time with `g = 2`.
4. Inside this inner call, the body says `return g(2)` again, but here `g` is `2`.
5. Python tries to evaluate `2(2)`, which is a **TypeError** because the integer `2` is not callable.

Therefore the behavior is:

- It prints `4`.
- It prints `6`.
- Then evaluating `f(f)` raises a `TypeError` before a third line can be printed.

So the correct choice is **C**.

1. Tracing Composition and Closures

This exercise connects closures (functions that remember values) with function composition.

Consider this code, which is very close to the slide on composition:

```python
def compose(f, g):
    def h(x):
        return f(g(x))
    return h

def make_adder(n):
    def adder(x):
        return x + n
    return adder

square = lambda x: x * x

add1 = make_adder(1)
f = compose(square, add1)
result = f(5)
print(result)
```

1. **Predict** (before running): what will this program print?
2. **Trace the calls** that happen when evaluating `f(5)`:
   - Which functions are called, and in what order?
   - For each call, what are the argument values (`x`, `n`, etc.)?
   - Which frame does each inner function (like `adder` and `h`) *close over*?

Use comments in the starter code to write your trace: show the sequence of calls and how the value `36` is computed step by step.

def compose(f, g):
    def h(x):
        return f(g(x))
    return h

def make_adder(n):
    def adder(x):
        return x + n
    return adder

square = lambda x: x * x

add1 = make_adder(1)
f = compose(square, add1)

# BEFORE running, write your prediction:
# I predict that result will be: __________

result = f(5)
print(result)

# TRACE THE CALLS (write your answers as comments):
# 1. Frame for make_adder(1): what is n?
#    - n = ______
#    - What does add1 remember about this frame?
#      Answer: ______________________________________
#
# 2. Frame for compose(square, add1): what are f and g?
#    - f (parameter) = _____________________________
#    - g (parameter) = _____________________________
#    - What does the returned function h remember?
#      Answer: ______________________________________
#
# 3. Call f(5): this is actually calling h(5).
#    - In h's frame, x = ______
#    - To compute f(g(x)), which function runs first: square or add1?
#      Answer: ______________________
#    - What argument does that inner function get?
#      Answer: ______________________
#
# 4. Call add1(5):
#    - In adder's frame, x = ______ and n = ______ (from closure)
#    - What does add1(5) return? ____________________
#
# 5. Now call square on that result:
#    - square( ______ ) = ______
#
# 6. Final result of f(5) is ______, so print should output ______.

Remember: `make_adder(1)` returns a **new function** whose body is `x + n`, and it remembers `n = 1`.

When you call `f(5)`, you are really calling the inner function `h` returned by `compose`.

In `return f(g(x))`, the call to `g(x)` happens **before** the call to `f(...)`.

1. **Prediction**

- `add1 = make_adder(1)` creates a closure where `n = 1`.
- `f = compose(square, add1)` creates a new function `h` such that `h(x) = square(add1(x))`.
- So `f(5)` computes `square(add1(5))`:
  - `add1(5) = 5 + 1 = 6`
  - `square(6) = 36`

So the program prints:

```text
36
```

2. **Call/Environment Trace for `f(5)`**

- **Global frame**:
  - Names: `compose`, `make_adder`, `square`, `add1`, `f`.

**Step A: `add1 = make_adder(1)`**
- Call `make_adder(1)`:
  - New frame `f1: make_adder` (parent = Global).
  - Binding: `n = 1`.
  - Inside this frame, Python defines `adder(x)`.
  - `adder` **closes over** `n = 1` from `f1: make_adder`.
  - `make_adder` returns this `adder` function; global name `add1` now refers to it.

**Step B: `f = compose(square, add1)`**
- Call `compose(square, add1)`:
  - New frame `f2: compose` (parent = Global).
  - Bindings: `f = square`, `g = add1`.
  - Inside this frame, Python defines `h(x)`.
  - `h` **closes over** `f` and `g` from `f2: compose`.
  - `compose` returns `h`; global name `f` now refers to this closure.

**Step C: `result = f(5)` (really `h(5)`)**
- Call `h(5)`:
  - New frame `f3: h` (parent = `f2: compose`).
  - Binding: `x = 5`.
  - Body: `return f(g(x))`.

  1. Evaluate `g(x)` **first**:
     - `g` is `add1` (the closure from `make_adder(1)`).
     - Call `add1(5)`:
       - New frame `f4: adder` (parent = `f1: make_adder`).
       - Binding: `x = 5`.
       - From the parent frame, `n = 1`.
       - Compute `x + n = 5 + 1 = 6`.
       - Return `6` to `h`.

  2. Now evaluate `f(g(x))` as `square(6)`:
     - `f` is `square` from the `compose` frame.
     - `square(6)` returns `36`.

  3. `h(5)` returns `36`.

- Global frame binds `result = 36`, and `print(result)` prints `36`.

So the trace confirms the final result is **36**, and illustrates two closures:
- `add1` remembers `n = 1`.
- `f` (really `h`) remembers both `square` and `add1`.

2. Repeated Application via Composition (SICP Ex 1.43)

In SICP Exercise 1.43, we define the *n-th repeated application* of a function.

If `f` is a one-argument function and `n` is a positive integer, the n-th repeated application of `f` is the function that applies `f` to its argument **n times**.

Examples:
- If `f(x) = x + 1`, then the n-th repeated application is `x ↦ x + n`.
- If `f(x) = x * x` (square), then the n-th repeated application raises its input to the `2^n` power.

You already saw composition on the slides:

```python
def compose(f, g):
    def h(x):
        return f(g(x))
    return h
```

### Task

1. **Predict** before implementing:
   - What should `repeated(lambda x: x + 1, 5)(3)` return?
   - What should `repeated(lambda x: x * x, 2)(5)` return?
   - What about `repeated(lambda x: x * x, 3)(2)`?
2. **Implement** `repeated(f, n)` so that it returns a new function that applies `f` a total of `n` times.
   - You may use recursion **or** a `while`/`for` loop.
   - Try to use `compose` from above in your solution, as suggested in SICP.

This exercise is based on **SICP Exercise 1.43** and extends the composition idea from the lecture.

def compose(f, g):
    """Return a function h such that h(x) == f(g(x))."""
    def h(x):
        return f(g(x))
    return h


def repeated(f, n):
    """Return a function that applies f n times.

    >>> inc = lambda x: x + 1
    >>> repeated(inc, 5)(3)  # inc applied 5 times: 3 -> 4 -> 5 -> 6 -> 7 -> 8
    8
    >>> square = lambda x: x * x
    >>> repeated(square, 2)(5)  # square(square(5)) = (5^2)^2 = 625
    625
    """
    # YOUR CODE HERE
    # You may assume n is a positive integer.
    pass


# Try your predictions here by uncommenting after you implement:
# inc = lambda x: x + 1
# square = lambda x: x * x
# print(repeated(inc, 5)(3))
# print(repeated(square, 2)(5))
# print(repeated(square, 3)(2))

Think about the **base case**: what should `repeated(f, 1)` return?

For `n > 1`, you can define `repeated(f, n)` in terms of `repeated(f, n-1)` and `compose`.

Alternatively, start with a function that just returns its input (identity), and then compose it with `f` in a loop `n` times.

One natural solution is recursive and uses `compose` directly, just like the SICP hint.

```python
def compose(f, g):
    def h(x):
        return f(g(x))
    return h


def repeated(f, n):
    """Return a function that applies f n times."""
    assert n >= 1, 'n must be a positive integer'
    if n == 1:
        # Applying f once: just f itself
        return f
    else:
        # Apply f once more after applying it n-1 times
        return compose(f, repeated(f, n - 1))
```

How this works:
- **Base case** `n == 1`:
  - `repeated(f, 1)` should apply `f` once, so it just returns `f`.
- **Recursive case** `n > 1`:
  - Assume `repeated(f, n-1)` is a function that applies `f` exactly `n-1` times.
  - Then `compose(f, repeated(f, n-1))` is a function that first applies `repeated(f, n-1)` (so `n-1` times), and then applies `f` once more, for a total of `n` applications.

Check the examples:

- `repeated(lambda x: x + 1, 5)(3)`:
  - Adds 1 five times: `3 → 4 → 5 → 6 → 7 → 8` → returns `8`.
- `square = lambda x: x * x`
  - `repeated(square, 2)(5)` = `square(square(5))` = `square(25)` = `625`.
  - `repeated(square, 3)(2)` = `square(square(square(2)))`:
    - `square(2) = 4`
    - `square(4) = 16`
    - `square(16) = 256`

These match the tests and the behavior described in SICP Ex 1.43.