Writing functional programs study guide

1. Start with the definition

When analysing a functional program, first identify the functions and the data passed to them. Ask whether a function is passed as an argument or returned as a result. If so, it is higher-order. This definition is more precise than simply saying that the function is reusable or that it processes a list.

Python provides built-in support for programming in a functional paradigm, so the following forms can be used to practise the required ideas. The same conceptual distinctions apply when constructing simple programs in a functional programming language such as Haskell, Standard ML, Scheme or Lisp.

2. Choose the operation from the required result

Use map when every element must be given to the same function and a list of results is required. For example, to double each value:

python values = [2, 4, 6] result = list(map(lambda value: value * 2, values))

Trace the operation element by element: 2 becomes 4, 4 becomes 8 and 6 becomes 12. The result is [4, 8, 12].

Use filter when the required result contains exactly the original elements that satisfy a condition:

python values = [2, 4, 6, 7, 9] result = list(filter(lambda value: value % 2 == 0, values))

The condition is tested on each element. The result is [2, 4, 6]. The values are selected rather than changed by the filtering operation.

Use reduce or fold when the required result is one value formed by repeatedly combining list values:

python from functools import reduce values = [2, 4, 6] result = reduce(lambda left, right: left + right, values)

The combining process can be traced as 2 + 4, followed by the result combined with 6, producing 12. The important reasoning point is that the intermediate result becomes an input to the next combination.

3. Distinguish the three mechanisms

A useful exam comparison is:

| Function | Role of supplied function | Shape of result | |---|---|---| | map | Calculates a result for each element | A list of results | | filter | Tests whether each element matches a condition | A data structure containing matching original elements | | reduce or fold | Combines values repeatedly | One value |

This table should not replace tracing. If given a program, state what the supplied function does, then follow the operation for each element or combination. For filter, explain which elements match. For reduce, explain the sequence of combinations.

4. Worked reasoning with composition

These operations can be used in sequence. For example:

python from functools import reduce values = [1, 2, 3, 4, 5, 6] even_values = filter(lambda x: x % 2 == 0, values) doubled_values = map(lambda x: x * 2, even_values) total = reduce(lambda a, b: a + b, doubled_values) result = list(doubled_values)

When explaining the intended processing, first identify the even values: [2, 4, 6]. Mapping the doubling function gives [4, 8, 12]. Reducing by addition gives 24. In actual Python evaluation, care is needed when using iterator results: converting an iterator to a list consumes it, so a program should materialise or inspect intermediate results in a suitable order. The conceptual functional stages remain filter, then map, then reduce.

5. Self-check questions

1. Why is map higher-order?
2. What is the difference between changing every element with map and retaining matching elements with filter?
3. Why does reduce or fold return one value rather than a list?
4. Given a list and a condition, which operation is appropriate, and what elements remain?
5. Given a list and a combining function, can you write every intermediate combination?

For each answer, use the formal definition and trace the data. Avoid vague statements such as “map sorts the list” or “filter calculates a total”; neither description identifies the required mechanism.