Writing functional programs revision notes

Functional programming

A functional language can be used to construct programs from functions. The AQA specification identifies Haskell, Standard ML, Scheme and Lisp as functional programming languages. It also identifies Python, F#, C#, Scala, Java 8, Delphi XE versions onwards and VB.NET 2008 onwards as languages with built-in support for programming in a functional paradigm as well as other paradigms. This means that, for this topic, Python can be used to demonstrate functional techniques.

Higher-order functions

A function is higher-order if it takes a function as an argument, returns a function as a result, or does both. The function supplied as an argument is used by the higher-order function to process data. This creates a distinction between the operation being requested and the function that describes how the operation should be carried out.

For example, in Python, map can apply a function to each element of a list:

python numbers = [1, 2, 3, 4] doubled = list(map(lambda x: x * 2, numbers))

The function lambda x: x * 2 is applied to every element. The result is a list containing the results, [2, 4, 6, 8]. map is therefore a higher-order function because it takes a function as an argument.

filter

filter processes a data structure, typically a list, and produces a new data structure containing exactly those original elements that match a given condition. The supplied function acts as the condition:

python numbers = [1, 2, 3, 4, 5, 6] even_numbers = list(filter(lambda x: x % 2 == 0, numbers))

The condition is true for 2, 4 and 6, so the resulting list is [2, 4, 6]. Unlike map, filter does not produce one transformed result for every input element; it selects elements that match the condition.

reduce or fold

reduce or fold reduces a list of values to one value by repeatedly applying a combining function to the list values. For example:

python from functools import reduce numbers = [1, 2, 3, 4] total = reduce(lambda a, b: a + b, numbers)

The combining function is applied repeatedly, giving a single result, 10. Thus, map normally preserves the number of list positions, filter can produce a shorter list, and reduce or fold produces one value from the list.

Common errors

Do not confuse the function supplied to a higher-order function with the data being processed. Do not describe filter as transforming every item: its purpose is to retain exactly the items matching a condition. Do not describe reduce as returning a list: its purpose is to reduce a list to a single value. Finally, remember that a function is higher-order because of its relationship with functions as inputs or outputs, not merely because it processes a list.