Functional Programming: Functions, Map, Filter and Fold

What is the functional paradigm?

A programming paradigm is a style of writing programs. In imperative programs you give step-by-step orders that change variables. In functional programs you describe the answer as functions applied to data.

Function, domain and co-domain

A function links every input to exactly one output. The set of allowed inputs is the domain. The set that outputs are taken from is the co-domain. We write the function type as f: A → B, meaning f takes a value from set A and gives a value in set B.

Example: isEven: integer → Boolean. Domain = integers, co-domain = {True, False}.

Pure functions and no side effects

• Pure: the same input always gives the same output.
• No side effects: the function does not change global variables, files or the screen.
• Immutable data: values are never changed; a new value is made instead.
• Referential transparency: you can replace a call by its result without changing the program.

Why it helps: code is easier to test, easier to prove correct, and safe to run on many processors at once.

First-class functions, partial application and composition

First-class functions

A function is first-class when it can be used like any other value: given a name, passed as an argument, returned as a result, and stored in a list.

Higher-order functions

A higher-order function takes a function as an argument or returns one. map, filter and fold are higher-order.

Partial application

Think of add x y = x + y as having type integer → (integer → integer). If you give it only 5, you get a new function add5 = add 5 of type integer → integer. Then add5 2 = 7.

Function composition

g ∘ f means apply f first, then g: (g ∘ f) x = g(f(x)). If f: A → B and g: B → C then g ∘ f: A → C. The co-domain of f must match the domain of g. Order matters: usually g ∘ f ≠ f ∘ g.

Lists: head, tail and list operations

In functional languages a list is either empty [], or a head (the first item) joined to a tail (a list of the rest).

• head [4,7,9] = 4
• tail [4,7,9] = [7,9]
• tail [9] = []; head of [] is an error
• Prepend: 2 : [7,9] = [2,7,9]
• Append: [7,9] ++ [2] = [7,9,2]
• Is empty? null [] = True; length [4,7,9] = 3

Because a list is head + tail, many list functions are written with recursion: do something with the head, then call the same function on the tail, and stop at the empty list.

total [] = 0
total (x:xs) = x + total xs

Map, filter and fold (reduce)

• map f list applies f to every item and returns a new list of the same length. map (*2) [1,2,3] = [2,4,6].
• filter p list keeps only items for which the test p is True. filter (>2) [1,2,3,4] = [3,4].
• fold f start list (also called reduce) combines all items into one value. fold (+) 0 [1,2,3] = ((0+1)+2)+3 = 6. Fold left works from the left; fold right works from the right, which matters for operations like subtraction.

They can be chained: sum of squares of even numbers in [1..6] = fold (+) 0 (map (^2) (filter even [1..6])) = 4 + 16 + 36 = 56.

Try it

In the last 3D step, choose map, filter or fold and slide the list length. Say your prediction aloud first. Then try in Python: list(map(lambda x: x*3, [1,2,3])), list(filter(lambda x: x%2, [1,2,3,4])) and functools.reduce(lambda a,b: a+b, [1,2,3], 0).

Key formulas and definitions

• Function type: f: A → B (A = domain, B = co-domain)
• Composition: (g ∘ f)(x) = g(f(x)); f: A → B and g: B → C give g ∘ f: A → C
• Partial application: add: int → (int → int); add 5 is a function int → int
• map f [x1, …, xn] = [f x1, …, f xn]
• filter p list = items x with p x = True
• fold f a [x1, x2, …, xn] = f(…f(f(a, x1), x2)…, xn)
• list = head : tail; head [a,b,c] = a; tail [a,b,c] = [b,c]

Worked examples

Common mistakes

• Thinking map can change the length of a list. map always returns a list of the same length; filter is the one that can make it shorter.
• Reading g ∘ f as 'g first'. In g ∘ f, f is applied first, then g.
• Taking the tail to be the last item. The tail is the whole list after the head, and it is always a list.
• Believing a pure function may print or change a global variable. Doing either is a side effect, so the function is no longer pure.