Sequences

From data abstraction to sequence abstraction

• Last time: abstraction barrier via $constructors/selectors$
• Today: sequences as a conventional interface
• Driving question: build programs as stages on a "signal"

A pipeline goal: select, transform, combine

$$ R = \sum_{\substack{1\le k\le 10\\ k\ \mathrm{odd}}} k^2 $$

• Stages: enumerate $\to$ select $\to$ transform $\to$ combine
• Same plan, many problems: sums, searches, transforms

Lists: the universal sequence (and they are closed under nesting)

• Sequence: ordered values, e.g. [1, 2, 3, 4]
• Closure idea: lists can contain other lists, e.g. [[1, 2], 3, 4]

Map: transform every element (separate "what" from "how")

• Definition idea: my_map(f, s) = [f(x) for x in s]
• Built-in: list(map(lambda x: x * x, [1, 2, 3, 4]))
• Predict: list(map(lambda x: x + 10, [1, 2, 3]))
• Result: [11, 12, 13] (each element gets 10 added: 1→11, 2→12, 3→13)

Filter: keep only elements that pass a test

• Definition idea: my_filter(p, s) = [x for x in s if p(x)]
• Built-in: list(filter(lambda x: x % 2 == 0, range(10)))
• Checkpoint (predict): list(filter(lambda x: x > 3, [1, 5, 2, 7, 3]))
• Compare: actual output is [5, 7] — why is 3 excluded when the test is x > 3?

Reduce (fold): combine a whole sequence into one value

$$ \operatorname{fold\text{-}right}(\oplus, z, [a_1,\dots,a_n]) = a_1 \oplus (a_2 \oplus (\cdots \oplus (a_n \oplus z))) $$

• Python: from functools import reduce (behaves like fold-left)
• Order matters when $\oplus$ is not associative, e.g. division

The signal-processing view: composition beats loops

• Predict: do these two expressions return the same number? What is it for 1 through 10?
• Pipeline code: sum(map(lambda x: x*x, filter(lambda x: x%2==1, range(1, 11))))
• Comprehension version: sum([x*x for x in range(1, 11) if x % 2 == 1])
• Confirm: both return 165
• Design win: swap stages without rewriting traversal

Iterators and generators: pipelines can be lazy

• Lazy idea: values produced "on demand"
• Generator example: def naturals(): n = 0 while True: yield n n += 1
• Composition: filter and map can stay lazy until sum

Exit ticket: build and explain a pipeline

• Practice: write a pipeline for $\sum k^3$ over $k\le n$ with $3\mid k$
• Reflection: when prefer a generator over a list?