Introduction to Functional Programming

Overview

This is an extremely brief and limited introduction to a few common functional programming constructs. For a more complete introduction, see Professor Frisby’s Mostly Adequate Guide to Functional Programming.

What is Functional Programming?

Many modern languages support some aspects of functional programming. The functional programming paradigm relies on pure functions and immutable data for program construction. A pure function has no side effects and no external dependencies, which means that its output is determined entirely by its explicit inputs. Data is immutable if it cannot be changed. In particular, names in a functional program generally refer to a constant value. In that sense, they are constants rather than variables. As a result, a name may be replaced by its value without changing the meaning of the program.

Computational and Mathematical Functions

Conceputalize a function as a transformation rule, which turns input (the function arguments) into output (the return value). Roughly speaking, a mathematical function maps any permissible input to a determinate output. (The set of permissible inputs is called the domain of the function.)

The word function is used much more loosely than this in computer science; it may refer to any subroutine that returns a value. A pure function is the computational analogue of a mathematical function. The output of a pure function is completely determined by its explicit inputs. If repeatedly given an unchanged input, a pure function always produces the same output.

A pure function explicitly returns a value that is deterministically related to its explicit inputs. There is no dependence on the global program state, not even the state of a (pseudo) random number generator. Just as importantly, a pure function does not produce any side-effects. In particular, the evaluation of a pure function does not change any global variables.

Example: Identity Function

Perhaps the simplest example of a pure function is the identity function, which we may express mathematically as \(x \mapsto x\). We often give functions names, to make it easier to refer to them. Call this function \(f\) for the moment. A common mathematical notation for binding this name to this function is \(f = x \mapsto x\).

These examples leave implicit the type of input (domain) and type of output (codomain). Some programming languages require that these be specified.

First Class Functions

In programming languages with support for functional programming, functions are first-class objects. This just means functions are treated like any other value: they can be passed to functions as arguments, returned from functions, and stored inside data structures.

Functional programming techniques focus on useful ways of combining pure functions. This often involves passing functions as arguments to other functions. Functions that take other functions as arguments are higher order functions. Examples include maps, filters, reductions, and compositions. (See below.)

Toward a More Declarative Programming Style

A programming style is considered to be imperative to the extent that it focuses on the explicit flow of control that leads to progress toward some goal by sequentially changing the global state of the program. Imperative programs focus on specifying control flow (with explicit loops and branches) and on variable assignments that change program state.

However, programmers do not usually need to see all the details of how a goal is accomplished. It is more help to simply declare what goal we want accomplished and rely on prior programming effort to accmplish it. That is, most of the time a more declarative style of programming is appropriate.

Relying on existing functions helps us focus on declaring what goal we want to achieve rather than on specifying what steps we want to take to accomplish a goal. This allows us to move towards a more declarative style of programming. In this sense, procedural programming is itself a step away from imperative programming towards declarative programming. Functional programming is a bigger step in this direction.

No while Loop

The standard while loop is available as an imperative looping construct in many programming languages. However, it is not a part of functional programming, because it generally relies on mutating some program value. (For example, incrementing a counter.)

Map

The mapping problem is the following: given a univariate function and a sequence of items, produce a new sequence of items transformed by the function. Mapping is also known as substitution. A traditional (imperative) approach to mapping is to create a a mutable sequence of the same size (perhaps by copying the original sequence) along wit a counter controlled loop that fills each location in the new sequence with the corresponding new value. Here is an example of this imperative approach in Python, where the new list holds the square of each element in the original list.

array01 = range(10)     #original sequence
def f(x): return x * x  #function to apply

array02 = list(array01) #new sequence (a copy)
n = len(array01)
ct = 0
while ct < n:
    array02[ct] = f(array01[ct])
    ct += 1

Mapping syntax provides a simpler and more intuitive approach to the mapping problem. Languages that support the functional programming paradigm typically provide a higher-order function named map. This is a higher-order function because it requires a function as an input argument. A map takes as inputs a univariate function and a collection of items. It applies the function to each item in the collection, thereby producing a new collection of items. (It is worth noting that when the function is pure, mapping is inherently parallelizable.)

Languages that support mapping often support function literals. This makes it easy to introduce one-off functions on the fly, as needed. The functions can remain anonymous (i.e., unnamed) because they will not be needed again, so they are often called anonymous functions. Here are some examples of squaring elements of a list using a map using a function literal.

NetLogo uses an arrow (->) to create a function literal. The formal parameters are introduced in brackets before the arrow. (The brackets may be omitted when there is only one variable.) The function body comes after the arrow. The entire construct must also be enclosed in brackets.

Python uses the lambda keyword to create a function literal. Formal parameters are placed the left of a colon; the function body is defined to the right of the colon. (A Python programmer is more likely to use a list comprehension than to map explicit use of map. However map more naturally supports function literals, and more importantly, in Python 3 map provides lazy evaluation.) WL has a variety of syntactical constructs for function literals, two of which are illustrated above.

Filter

The filtering problem is the following: given a univariate predicate and a sequence of items, produce a new collection of items transformed by the function. (A univariate predicate is a univariate boolean function.) Filtering is also known as selection. A traditional (imperative) approach to filtering is build up a sequence by sequentially appending items, using a counter controlled loop. Here is an example in Python, where the new list is a filtered version of the original list.

::

array01 = range(10) #original sequence def f(x): return (x < 5) #predicate to apply

array02 = list() #empty list n = len(array01) ct = 0 while ct < n:

item = array01[ct] if f(item):

array02.append(item)

ct += 1

Whether an item is retained or discarded depends on the predicate, which is a boolean valued function. (That is, it returns True or False.) In the examples below, the predicate is applied to the each item of the collection. The resulting new collection comprises the items that the predicate evaluated as true. Filtering is therefore sometimes called subsetting. (Note however that the original collection and the outputs may contain duplicates.)

Counting with Maps and Filters

The criterion-based counting problem is the following: given a sequence of items, produce a count of the number of items that satisfy a criterion. For example, given a list of numbers, produce a count of the positive numbers. As another example, given a list of strings, produce a count of one character strings. Here are two approaches, using maps and filters. (A third approach is discussed below.) To use a map, just map every item to \(1\) or \(0\) depending on whether or not the criterion is satisfied, and then sum these results. To use a filter, just filter on the criterion, and then report the length of the result. These approaches assume that the language provides a builtin way to produce a sum over numerical sequences or a length of a sequence, but these are commonly provided facilities.

Map and Filter vs Explicit Loops

Map and filter are declarative: they require only a statement of the core goal and dispense with many imperative details. Explicit loops are imperative, providing all the steps for achieving the desired outcome.

Map and filter have some advantages over corresponding imperative loops. Most obviously, they are easier to read. Part of this ease comes from the absence of auxiliary variables, and this reflects the absence of side effects. Part of this ease comes from the more declarative style, where the programmer more clearly states the goals just by writing down a map or filter.

As an aside, many functional languages allow a syntax similar to mathematical set-building notation for the implementation of maps and filters. For example, Python includes list comprehensions, where one can write the above filter as [x for x in [-2, -1, 0, 1, 2] if x>0]

Reduce

The reduction problem is the following: given a bivariate function and a sequence of values, produce a single new value by sequentially combining the original values. This is sometimes called folding or aggregation. While a reduction also takes as inputs a function and a collection of items, this time the function is bivariate. (That is, it requires two values as arguments.) A traditional (imperative) approach to reduction is to build up a value by sequentially applying the bivariate function, using a counter controlled loop. Here is an example in Python, where the final value of acc is a reduction of the original list.

array01 = range(10)           #original sequence
def f(a, c): return (a + c)   #bivariate function

acc = array01[0]              #starting value
n = len(array01)
ct = 1
while ct < n:
    item = array01[ct]
    acc = f(acc, item)
    ct += 1

In the examples below, the function is applied to the first two items of the collection, and then repeatedly to the result and the next item. In this way, it produces a value that is created by repeatedly combining the items in the collection. (For the Python example, you must first from functools import reduce.)

Conditional Expression

A computational expression can be evaluated. Evaluation produces a value. A conditional expression has a value that depends on a condition. This value is produced by evaluating one expression if the condition is true and another if the condition is false. Crucially, languages that support conditional expressions do not evaluate the bypassed expression. So the following evaluate safely even if x = 0.

Counting as Reduction

Recall that the criterion-based counting problem is the following: given a sequence of items, produce a count of the number of items that satisfy a criterion. This is a natural application of folding, but it introduces two new wrinkles: we need to provide a starting count of \(0\) for the accumulator, and the type of the result may differ from the type of the items. (E.g., a number is not a string.) A traditional (imperative) approach to this problem is to build up a value by sequentially applying the bivariate function, using a counter controlled loop. Here is an example in Python, where the final value of \(acc\) is a reduction of the original list.

array01 = range(10)                           #original sequence
def f(a, c): return (a + (1 if c > 0 else 0)  #bivariate function

acc = 0                                       #starting value
n = len(array01)
ct = 0
while ct < n:
    item = array01[ct]
    acc = f(acc, item)
    ct += 1

We will now do this in a more functional (declarative) way. In the examples below, the function is first applied to the initializer and the first item of the collection, and then repeatedly to the result and the next item. This performs a reduction: it produces a single value that is created by repeatedly combining the items in the collection.

If we want to get sensible results for an empty list, we need to initialize the accumulator. Python’s reduce allows for a third argument, which intializes the accumulator.

from functools import reduce  #Python 3+
reduce(lambda a,c: a+(1 if c>0 else 0), [-2, -1, 0, 1, 2], 0)

The reduce method accepts a second argument, which is used to initialize the accumulator.

[-2,-1,0,1,2].reduce((a,c)=>a+(c>0?1:0), 0)

WL’s Fold has a three-argument form, where the second argument intializes the accumulator.

Fold[#1+If[#2>0,1,0]&, 0, {-2, -1, 0, 1, 2}]

NetLogo does not offer a direct way to initialize the accumulator. It is therefore conventional to use fput to insert an initial value for the accumulator at the beginning of the list of items.

reduce [[a c] -> a + ifelse-value (c > 0) [1][0]] (fput 0 [-2 -1 0 1 2])

Julia requires a name for keyword argument, and therefore to initialize the accumulator. Note that reduce makes no guarantee about the order in which elements of the sequence are considered. (If this matters, use foldl or foldr instead.)

reduce((a,c) -> a+(c>0 ? 1 : 0), [-2, -1, 0, 1, 2]; init=0)

Pipelines and Composition

Fundamental to functional programming is the idea that we can use the output of one function as the input to the next. A program becomes largely a “pipeline” of functions, which provide sequential processing of an initial input. Such pipelining is a computational equivalent to mathematical function composition. While functionally oriented programming languages often provide explicit support for function composition, functional programming in other languages must rely on pipelining.

Cook (2017) suggests implementing a pipelining utility in Python as follows:

def pipeline_each(data, fns):
  return reduce(lambda a, x: map(x, a), fns, data)

Additional Functional Jargon

Curry

Decompose a multivariate function into a composition of univariate functions.

Immutable object

A piece of data one that cannot be changed. Some languages, like Clojure and Haskell, make all values immutable by default. Other languages, like Python and NetLogo, provide both mutable and immutable data types. With immutable objects, one part of a program never needs to worry that another part changed the object. This helps to increase referential transparency.

Referential Transparency

An expression is referentially transparent if replacing it by its value cannot change the behavior of the program. A function breaks referential transparency if it returns a value that depends on anything other than its explicit inputs. So for example, a function whose body refers to a global variable is not referentially transparent. Referential transparency eliminates uncertainty about the value associated with an identifier.

Tail call optimisation

A tail call is a function call at the very end of the function. If the tail call of a function calls the function itself, it is a recursive tail call. A function that calls itself is said to recurse. Some forms of recursion are easier to accommodate than others. Tall call recursion can be specially handled, and some languages provide explicit support for this.

Ordinarily, each time a function recurses, a new stack frame is created. (A stack frame stores the arguments and local values for the current function call.) If a function recurses a large number of times, the call stack may exhaust available memory. Some languages can reuse a single stack frame for an entire sequence of recursive tail calls; this is called tail call elimination. Most languages, including Python and NetLogo, do not have tail call elimination. Instead, they limit the number of times a function may recurse. Functionally oriented languages generally provide tail call elimination, eliminating the need to use loops in order to conserve memory.

Parallelization

Parallel processing takes place concurrently but asynchronously on multiple cores, processors, or even machines. Functional programs are easier to parallelize.

Lazy evaluation

Postponing code execution until a value is actually needed is called lazy evaluation. This compiler technique avoids executing some code until the result is needed to execute other code. Functional programming languages often support lazy evaluation.