Sequences Lab: Pipelines with map, filter, and folds

Practice building programs as sequence pipelines (select → transform → combine), predict behavior before running, trace lazy iterator flow, and implement pipelines using fold/accumulate (SICP-inspired).

0. Predict a Pipeline Result (odd squares)

**Predict the output** before running:

```python
def odd_square_sum(n):
    return sum(map(lambda x: x * x,
                   filter(lambda x: x % 2 == 1, range(1, n + 1))))

print(odd_square_sum(10))
print(odd_square_sum(1))
```

What will be printed?

A) `165` then `1`
B) `220` then `1`
C) `165` then `0`
D) Error (because `map`/`filter` are iterators)

def odd_square_sum(n):
    return sum(map(lambda x: x * x,
                   filter(lambda x: x % 2 == 1, range(1, n + 1))))

# Prediction (write BEFORE running):
# I predict the two printed lines are:
# 1) ???
# 2) ???

# Uncomment to check:
# print(odd_square_sum(10))
# print(odd_square_sum(1))

Stages: range(1..n) → filter odd → square each → sum.

For n=10, the odd numbers are 1,3,5,7,9.

`sum(...)` can consume an iterator (so no error).

def odd_square_sum(n):
    return sum(map(lambda x: x * x,
                   filter(lambda x: x % 2 == 1, range(1, n + 1))))

# odd_square_sum(10) = 1^2+3^2+5^2+7^2+9^2 = 165
# odd_square_sum(1) = 1

1. Trace Laziness: Who Gets Pulled From the Source?

This exercise models a *lazy pipeline* by recording events instead of printing.

1) **Trace** which `source` elements are demanded to produce `a = next(it)`.
2) Then trace what happens when we consume the rest with `list(it)`.

```python
def run():
    out = []
    def source():
        for x in [1, 2, 3, 4]:
            out.append(f"source {x}")
            yield x

    it = map(lambda x: x * x,
             filter(lambda x: x % 2 == 0, source()))

    a = next(it)
    out.append(f"a {a}")

    b = list(it)
    out.append(f"b {b}")

    return out
```

**Task**: Before running, write the exact list that `run()` returns.

Then run it to confirm.

def run():
    out = []

    def source():
        for x in [1, 2, 3, 4]:
            out.append(f"source {x}")
            yield x

    it = map(lambda x: x * x,
             filter(lambda x: x % 2 == 0, source()))

    # Trace questions (answer as comments):
    # Q1: Which 'source x' entries must happen before a = next(it) succeeds?
    # Q2: After that, when b = list(it) runs, which remaining 'source x' entries happen?
    # Q3: Why does 'source 3' appear even though 3 is filtered out?

    a = next(it)
    out.append(f"a {a}")

    b = list(it)
    out.append(f"b {b}")

    return out

# Prediction (write BEFORE running):
# I predict run() returns:
# [ ... ??? ... ]

# Uncomment to check:
# print(run())

`filter` must *inspect* each incoming element to decide keep/drop.

`next(it)` pulls just enough from the source to produce one mapped value.

Even filtered-out items still get pulled from the source (they're just not passed onward).

def run():
    out = []

    def source():
        for x in [1, 2, 3, 4]:
            out.append(f"source {x}")
            yield x

    it = map(lambda x: x * x,
             filter(lambda x: x % 2 == 0, source()))

    # next(it) needs the first even source value.
    # It will pull 1 (drop), then 2 (keep) and square it.
    a = next(it)
    out.append(f"a {a}")

    # list(it) consumes the rest of the pipeline.
    # It pulls 3 (drop), then 4 (keep) and squares it.
    b = list(it)
    out.append(f"b {b}")

    return out

2. Accumulate Builds Pipelines (SICP Ex 2.33 + Exit Ticket)

In SICP, many sequence operations are built from a single pattern: **accumulation** (fold).

Implement `accumulate` as a **fold-right**:

\[ accumulate(op, z, [a1,a2,...,an]) = op(a1, op(a2, ... op(an, z))) \]

Then use it to build `my_map` and `my_filter` (no explicit loops).

Finally, **extend** it into an exit-ticket pipeline:

> `sum_cubes_div_by_3(n)` returns \( \sum k^3 \) over integers \(1 \le k \le n\) where \(3 \mid k\).

Write your prediction for `sum_cubes_div_by_3(10)` before running tests.

def accumulate(op, z, seq):
    """Fold-right accumulation.

    accumulate(op, z, [a1, a2, ..., an])
      = op(a1, op(a2, ... op(an, z)))

    >>> accumulate(lambda x, y: x - y, 0, [1, 2, 3])
    2
    """
    # YOUR CODE HERE
    pass


def my_map(f, seq):
    """Return [f(x) for x in seq], but built from accumulate."""
    # YOUR CODE HERE
    pass


def my_filter(pred, seq):
    """Return [x for x in seq if pred(x)], but built from accumulate."""
    # YOUR CODE HERE
    pass


def sum_cubes_div_by_3(n):
    """Exit ticket pipeline.

    Return sum(k^3 for k in 1..n if k % 3 == 0).

    Prediction prompt:
    - I predict sum_cubes_div_by_3(10) == ???
    """
    # YOUR CODE HERE
    pass

For fold-right: if seq is empty, return z; otherwise return op(first, accumulate(op, z, rest)).

To build a list without mutation: use list concatenation like [item] + rest_list.

For my_filter: your combining function can decide whether to prepend x or skip it.

For sum_cubes_div_by_3: think stages: enumerate → filter → map (cube) → combine (sum).

def accumulate(op, z, seq):
    if seq == []:
        return z
    return op(seq[0], accumulate(op, z, seq[1:]))


def my_map(f, seq):
    return accumulate(lambda x, xs: [f(x)] + xs, [], list(seq))


def my_filter(pred, seq):
    return accumulate(lambda x, xs: ([x] + xs) if pred(x) else xs, [], list(seq))


def sum_cubes_div_by_3(n):
    cubes = my_map(lambda k: k * k * k,
                   my_filter(lambda k: k % 3 == 0, range(1, n + 1)))
    return accumulate(lambda x, y: x + y, 0, cubes)