Lambda and Higher-Order Functions

In the previous lesson, both the filter condition and the item expression stayed embedded inside the comprehension. Both stated a rule — “let this through,” “turn this into that” — but the rule could not be used outside where it was written. Repeating the same filter in a second comprehension meant writing it again.

Rules can be named. A function is exactly this: a named rule. This lesson’s question is whether that function can be passed as an argument, and how many times it is called when it is. Is a sort’s key computed once per item, or freshly on every comparison? The gap between the two will produce two numbers on two hundred items, and they will not be the same order of magnitude.

A Function Is an Object

In Python, def is not a declaration, it is a statement: when run, it produces a function object and binds it to a name. The binding is like any other — the object can go into a list, be a value in a dict, be passed as an argument to a function, be returned from a function.

lambda produces the same kind of object without binding a name. It carries a single expression, return is not written, its result is the expression’s value. The produced object is the same type as what def produces; the only place they differ is the name it carries.

A function that takes a function as an argument or returns one is called a higher-order function. The Programming Fundamentals course built this concept at the entrance to functional programming; it is not repeated here. What is measured is how many times Python’s built-in higher-order functions call the given function, and how many objects they materialize.

The Key Function’s Contract

sorted, min, and max accept a key argument: a function giving the comparison value computed for each item. The contract’s measurable side is this — how many times per item is this function called?

Two answers come to mind. Sorting compares items with each other, and comparison count exceeds item count; if the key is computed on every comparison, call count would be the same. Or the key is computed once and stored, and comparisons run on the stored values. The second route lowers call count but raises retention: a key value has to stay alive for every item. The measurement says which one holds.

The measurement’s assumptions:

• IF36 — The shared reference’s Item class is used as is, with its counting arrangement; Item only counts production, key calls are kept in a separate counter.
• IF37 — The key function counts every call to itself; the measure for “how many times was it called” is this counter, and it is the oracle itself.
• IF38 — The source has 200 items, and all four operations run on the same source. The counter is reset before every operation.
• IF39 — The key value is computed with -o.value % 97; the number is arbitrary and chosen only so sorting produces an order different from the source’s.
• IF40 — The hand-written selection sort computes the key twice per comparison; this is the behavior of a notation that does not store the key, and is the measurement’s opposite end. Sorting is used here not as an algorithm but as a rig producing a call count.
• IF41 — The distinction between sorted and list.sort is measured by identity; identity is shown with is, no number is printed.
• IF42 — In the map and filter measurement, the counter is read right after the setup line; the item-producing function deliberately produces new Items, so laziness becomes visible through production.
• IF43 — That the three functions are separate objects is shown with pairwise is comparisons; no identity number is printed.
• IF44 — In the binding measurement, all three notations build the same three functions, and all are called with the same item; the only thing that changes is where the factor is written.

Measurement

"""Function is an object: how many times is the key function called, when does a stream materialize."""

import functools

COUNTER = {"produced": 0, "key_calls": 0}


class Item:
    """An item that counts every production of itself."""

    def __init__(self, value):
        COUNTER["produced"] += 1
        self.value = value

    def __repr__(self):
        return f"Item({self.value})"


def reset():
    COUNTER["produced"] = 0
    COUNTER["key_calls"] = 0


def produced():
    return COUNTER["produced"]


def key_function(o):
    """The item's sort key; counts every call to itself."""
    COUNTER["key_calls"] += 1
    return -o.value % 97


N = 200
SOURCE = [Item(i) for i in range(N)]


def manual_select(items, key):
    """Selection sort that recomputes the key on every comparison."""
    remaining, ordered = list(items), []
    while remaining:
        min_idx = 0
        for i in range(1, len(remaining)):
            if key(remaining[i]) < key(remaining[min_idx]):
                min_idx = i
        ordered.append(remaining.pop(min_idx))
    return ordered


OPERATIONS = (("sorted(n, key=f)", lambda n: len(sorted(n, key=key_function))),
            ("min(n, key=f)", lambda n: min(n, key=key_function)),
            ("max(n, key=f)", lambda n: max(n, key=key_function)),
            ("manual selection sort", lambda n: len(manual_select(n, key_function))))

print(f"{'operation':<24s} {'key calls':>16s} {'per item':>11s}")
for name, operation in OPERATIONS:
    reset()
    operation(SOURCE)
    print(f"  {name:<22s} {COUNTER['key_calls']:16d} {COUNTER['key_calls'] / N:11.1f}")

reset()
ordered = sorted(SOURCE, key=key_function)
print()
print(f"sorted(n) is n -> {ordered is SOURCE}, materialized {produced()},"
      f" shared {sum(1 for o in ordered if any(o is k for k in SOURCE))}")
copy = list(SOURCE)
before = copy
result = copy.sort(key=key_function)
print(f"list.sort return value {result!r}, container stayed the same -> {before is copy}")


def named(o):
    return o.value


unnamed = lambda o: o.value
print()
print(f"{'function':<12s} {'callable':>13s} {'__name__':>12s} {'same type':>12s}")
for name, f in (("via def", named), ("via lambda", unnamed)):
    print(f"  {name:<10s} {str(callable(f)):>13s} {f.__name__:>12s}"
          f" {str(type(f) is type(named)):>12s}")

REGISTRY = {"increment": lambda o: o.value + 1, "double": lambda o: o.value * 2}
print(f"functions held in dict: {sorted(REGISTRY)},"
      f" REGISTRY['double'](Item(21)) -> {REGISTRY['double'](Item(21))}")

reset()
mapped = map(lambda o: Item(o.value * 2), SOURCE)
filtered = filter(lambda o: o.value % 2 == 0, SOURCE)
at_setup = produced()
first = next(mapped)
print()
print(f"map and filter materialized {at_setup} objects at setup,"
      f" once the first item is requested {produced()}")
print(f"once fully walked: map {len(list(mapped)) + 1} items,"
      f" filter {len(list(filtered))} items, materialized {produced()}")

reset()
total = functools.reduce(lambda a, o: a + o.value, SOURCE, 0)
print(f"total via reduce {total}, materialized {produced()}")


def factor_maker(k):
    def multiply(o):
        return o.value * k
    return multiply


three_funcs = [factor_maker(k) for k in (1, 2, 3)]
separate = all(a is not b for i, a in enumerate(three_funcs) for b in three_funcs[i + 1:])
print()
print(f"are the three functions separate objects -> {separate},"
      f" results {[f(Item(10)) for f in three_funcs]}")
print(f"factor_maker(2) is factor_maker(2) -> "
      f"{factor_maker(2) is factor_maker(2)}")

late = [lambda o: o.value * k for k in (1, 2, 3)]
early = [lambda o, k=k: o.value * k for k in (1, 2, 3)]
partial = [functools.partial(lambda o, k: o.value * k, k=k) for k in (1, 2, 3)]
print()
print(f"{'binding form':<26s} {'objects':>7s} {'results':>16s}")
for name, funcs in (("free name in body", late), ("default argument", early),
                ("via partial", partial)):
    print(f"  {name:<24s} {len(funcs):7d} {str([f(Item(10)) for f in funcs]):>16s}")

operation                       key calls    per item
  sorted(n, key=f)                    200         1.0
  min(n, key=f)                       200         1.0
  max(n, key=f)                       200         1.0
  manual selection sort             39800       199.0

sorted(n) is n -> False, materialized 0, shared 200
list.sort return value None, container stayed the same -> True

function          callable     __name__    same type
  via def             True        named         True
  via lambda          True     <lambda>         True
functions held in dict: ['double', 'increment'], REGISTRY['double'](Item(21)) -> 42

map and filter materialized 0 objects at setup, once the first item is requested 1
once fully walked: map 200 items, filter 100 items, materialized 200
total via reduce 19900, materialized 0

are the three functions separate objects -> True, results [10, 20, 30]
factor_maker(2) is factor_maker(2) -> False

binding form               objects          results
  free name in body              3     [30, 30, 30]
  default argument               3     [10, 20, 30]
  via partial                    3     [10, 20, 30]

One Call Per Item

The top table’s first three rows give the same number: 200 calls, exactly 1.0 per item. Sorting, finding the minimum, finding the maximum — in all three, the key function is called once per item, no more.

For min and max this is expected; looking at each item once is enough. For sorted it is not. Sorting has to compare items with each other, and comparison count exceeds item count. Yet the key call stays at 200: keys must be computed once and stored, with all comparisons run on the stored values.

The fourth row shows the opposite end of this decision. A sort doing the same job, never storing the key and recomputing it on every comparison, calls the key 39800 times on the same two hundred items — 199.0 per item. The ratio between the two numbers is two hundred, and it grows as item count grows.

Read from the course’s axis: built-in sorted makes a trade. Storing key values means holding as many references as there are items; in exchange, call count drops to item count. The notation avoiding retention — the fourth row — stores no intermediate value and pays with call count instead. This is the second lesson’s result reversed: there, the non-retaining form won; here, the retaining form wins. What is retained matters as much as what retaining removes.

This measurement is not a sorting-algorithm comparison; algorithms and complexity analysis are the Algorithms course’s subject. The fourth row here was hand-built only to show how many calls a notation not storing the key produces.

New Container or In Place

The next two lines separate two notations of the same job. sorted produces a new list: sorted(n) is n is false, materialized Item is 0, shared is 200. Sorting duplicates no items, it only writes them into a new container in a different order — the same container-building measurement from the first lesson.

list.sort builds no new container: the container stays the same and the return value is None. This is the shared signature of in-place methods in Python, and it has a consequence — the notation n = n.sort() replaces the list with None. The distinction shows in one line: want the result, use sorted; want to keep the container, use sort.

Proof That a Function Is an Object

The middle table compares two functions and gives the same answer on two of three columns. The objects defined with def and produced with lambda are both callable, both the same type. The only column they differ on is __name__: one carries its own name, the other <lambda>.

This single difference looks minor but is a preview of the next lesson’s measurement. A function object carries its own name in an attribute, and that attribute is used in error traces, log records, and documentation generation. A nameless object cannot give this information.

The next line shows the practical payoff of being an object: two functions sit as values in a dict and get called by key. The rule now lives in the same place as data — nameable, storable, passable. The filter that stayed embedded in the previous lesson’s comprehension could have been a dict value here.

Lazy Higher-Order Built-ins

The last three lines measure the map and filter built-ins, and a familiar number comes out: 0 objects at setup. Both return a stream; the given function is never called at setup time. Once the first item is requested, produced becomes 1; once fully walked, 200.

This is the third lesson’s claim, restated on built-ins: map does not avoid production, it defers it. Requesting two hundred items births two hundred objects. Filtering follows the same pattern and lets 100 of two hundred items through; no new object is built for the ones that do not pass, so production stays at two hundred.

The choice between map and a comprehension is therefore not a cost choice, it is a notation choice — one gives a stream, the other a container. Their numbers were measured in the previous two lessons and do not change here.

The last line shows a third higher-order tool: the standard library’s reduce function applies a two-argument function across a stream and collapses it into a single value. Total is 19900, materialized 0 — no intermediate container is built, only the accumulating value is carried at every step. A comprehension produces a container, map a stream, reduce a value; all three take the same function as an argument.

A Function That Returns a Function

The last two blocks reverse the direction: a function is now not an argument but a return value.

When factor_maker is called, the def inside its body runs and produces a new function object. Three calls give three separate objects, and three produce separate results — each carrying its own factor. Even two calls with the same argument give separate objects: factor_maker(2) is factor_maker(2) is false. Producing a function means materializing an object every time; ten separate factors mean ten separate function objects.

The Programming Fundamentals course’s closures — an inner function carrying an outer scope’s name — was built as a concept; the only thing added here is measuring that carrying by object count, and that what is carried is not a value but a name. The last table gives the consequence of this distinction.

All three notations produce three functions, and object count is 3 in all three. But the results are not the same. The free name in body form gives [30, 30, 30]: all three functions look at the same name k, and by the time they are called, that name’s last value is 3. The closure did not copy k’s value, it bound to its name.

The default argument form gives [10, 20, 30]. The Programming Fundamentals course’s function-definition lesson measured that a default value is evaluated once, at definition time; there it was a trap, here it is the fix. Since the value is computed at definition time, each function carries its own factor along. The standard library’s partial tool gives the same result by binding the argument in advance.

The three rows are three readings of the same notation, and the difference between them is the difference between a name and a value. In a comprehension, the loop name vanishes once the comprehension ends; the function bound to it does not vanish and sees the last value. Binding to a name is not the same as taking a value.

Summary

• def is a statement producing a function object; lambda gives the same kind of object without binding a name. Both are callable, both the same type, and the only place they differ is __name__.
• A function object can be held as a value in a container and passed as an argument; a function taking or returning a function is higher-order.
• On two hundred items, the key function for sorted, min, and max is called 200 times — exactly once per item. A hand-written sort not storing the key calls the same function 39800 times.
• sorted builds a new container and shares 200 items, duplicating none; list.sort runs in place and returns None.
• map and filter materialize 0 objects at setup, 200 once fully walked; filtering lets 100 of two hundred items through. reduce collapses to a single value without building any container.

Next Step

In this lesson functions always passed as arguments; none of them was changed. Yet if a function can be returned, it is also possible to take a function and return another function in its place — a wrapper that preserves the original behavior and adds something around it. The next lesson measures this pattern: how many objects does wrapping a function materialize, what happens to the original object, and what does the wrapped function’s __name__ attribute say? This lesson’s one seemingly minor column will produce a result there.