4.12 Fundamentals of functional programming

Functional programming paradigm

Function type

Content	Additional information
Know that a function, f, has a function type f: A → B (where the type is A → B, A is the argument type, and B is the result type). Know that A is called the domain and B is called the co-domain. Know that the domain and co-domain are always subsets of objects in some data type.	Loosely speaking, a function is a rule that, for each element in some set A of inputs, assigns an output chosen from set B, but without necessarily using every member of B. For example, f: {a,b,c,…z} → {0,1,2,…,25} could use the rule that maps a to 0, b to 1, and so on, using all values which are members of set B. The domain is a set from which the function’s input values are chosen. The co-domain is a set from which the function’s output values are chosen. Not all of the co-domain’s members need to be outputs.

Content

Additional information

Know that a function, f, has a function type

f: A → B (where the type is A → B, A is the argument type, and B is the result type).

Know that A is called the domain and B is called the co-domain.

Know that the domain and co-domain are always subsets of objects in some data type.

Loosely speaking, a function is a rule that, for each element in some set A of inputs, assigns an output chosen from set B, but without necessarily using every member of B. For example,

f: {a,b,c,…z} → {0,1,2,…,25} could use the rule that maps a to 0, b to 1, and so on, using all values which are members of set B.

The domain is a set from which the function’s input values are chosen.

The co-domain is a set from which the function’s output values are chosen. Not all of the co-domain’s members need to be outputs.

First-class object

Content	Additional information
Know that a function is a first-class object in functional programming languages and in imperative programming languages that support such objects. This means that it can be an argument to another function as well as the result of a function call.	First-class objects (or values) are objects which may: appear in expressions be assigned to a variable be assigned as arguments be returned in function calls. For example, integers, floating-point values, characters and strings are first class objects in many programming languages.

Function application

Content	Additional information
Know that function application means a function applied to its arguments.	The process of giving particular inputs to a function is called function application, for example add(3,4) represents the application of the function add to integer arguments 3 and 4. The type of the function is f: integer x integer → integer where integer x integer is the Cartesian product of the set integer with itself. Although we would say that function f takes two arguments, in fact it takes only one argument, which is a pair, for example (3,4).

Content

Additional information

Know that function application means a function applied to its arguments.

The process of giving particular inputs to a function is called function application, for example add(3,4) represents the application of the function add to integer arguments 3 and 4.

The type of the function is

f: integer x integer → integer

where integer x integer is the Cartesian product of the set integer with itself.

Although we would say that function f takes two arguments, in fact it takes only one argument, which is a pair, for example (3,4).

Partial function application

Content	Additional information
Know what is meant by partial function application for one, two and three argument functions and be able to use the notations shown opposite.	The function add takes two integers as arguments and gives an integer as a result. Viewed as follows in the partial function application scheme: add: integer → (integer → integer) add 4 returns a function which when applied to another integer adds 4 to that integer. The brackets may be dropped so function add becomes add: integer → integer → integer The function add is now viewed as taking one argument after another and returning a result of data type integer.

Content

Additional information

Know what is meant by partial function application for one, two and three argument functions and be able to use the notations shown opposite.

The function add takes two integers as arguments and gives an integer as a result. Viewed as follows in the partial function application scheme:

add: integer → (integer → integer)

add 4 returns a function which when applied to another integer adds 4 to that integer.

The brackets may be dropped so function add becomes add:

integer → integer → integer

The function add is now viewed as taking one argument after another and returning a result of data type integer.

Composition of functions

Content	Additional information
Know what is meant by composition of functions.	The operation functional composition combines two functions to get a new function. Given two functions f: A → B g: B → C function g ○ f, called the composition of g and f, is a function whose domain is A and co-domain is C. If the domain and co-domains of f and g are ℝ, and f(x) = (x + 2) and g(y) = y³. Then g ○ f = (x + 2)³ f is applied first and then g is applied to the result returned by f.

Content

Additional information

Know what is meant by composition of functions.

The operation functional composition combines two functions to get a new function.

Given two functions

f: A → B

g: B → C

function g ○ f, called the composition of g and f, is a function whose domain is A and co-domain is C.

If the domain and co-domains of f and g are ℝ, and f(x) = (x + 2) and g(y) = y³. Then

g ○ f = (x + 2)³

f is applied first and then g is applied to the result returned by f.

Writing functional programs

Functional language programs

Content	Additional information
Show experience of constructing simple programs in a functional programming language.	The following is a list of functional programming languages that could be used: Haskell Standard ML Scheme Lisp. Other languages with built-in support for programming in a functional paradigm as well as other paradigms are: Python F# C# Scala Java 8 Delphi XE versions onwards VB.NET 2008 onwards.
Higher-order functions.	A function is higher-order if it takes a function as an argument or returns a function as a result, or does both.
Have experience of using the following in a functional programming language: map filter reduce or fold.	map is the name of a higher-order function that applies a given function to each element of a list, returning a list of results. filter is the name of a higher-order function that processes a data structure, typically a list, in some order to produce a new data structure containing exactly those elements of the original data structure that match a given condition. reduce or fold is the name of a higher-order function which reduces a list of values to a single value by repeatedly applying a combining function to the list values.

Content

Additional information

Show experience of constructing simple programs in a functional programming language.

The following is a list of functional programming languages that could be used:

Haskell
Standard ML
Scheme
Lisp.

Other languages with built-in support for programming in a functional paradigm as well as other paradigms are:

Python
F#
C#
Scala
Java 8
Delphi XE versions onwards
VB.NET 2008 onwards.

Higher-order functions.

A function is higher-order if it takes a function as an argument or returns a function as a result, or does both.

Have experience of using the following in a functional programming language:

map
filter
reduce or fold.

map is the name of a higher-order function that applies a given function to each element of a list, returning a list of results.

filter is the name of a higher-order function that processes a data structure, typically a list, in some order to produce a new data structure containing exactly those elements of the original data structure that match a given condition.

reduce or fold is the name of a higher-order function which reduces a list of values to a single value by repeatedly applying a combining function to the list values.

Lists in functional programming

List processing

Content	Additional information
Be familiar with representing a list as a concatenation of a head and a tail. Know that the head is an element of a list and the tail is a list. Know that a list can be empty. Describe and apply the following operations: return head of list return tail of list test for empty list return length of list construct an empty list prepend an item to a list append an item to a list. Have experience writing programs for the list operations mentioned above in a functional programming language or in a language with support for the functional paradigm.	For example, in Haskell the list [4, 3, 5] can be written in the form head:tail where head is the first item in the list and tail is the remainder of the list. In the example, we have 4:[3, 5]. We call 4 the head of the list and [3, 5] the tail. [] is the empty list.

Content

Additional information

Be familiar with representing a list as a concatenation of a head and a tail.

Know that the head is an element of a list and the tail is a list.

Know that a list can be empty.

Describe and apply the following operations:

return head of list
return tail of list
test for empty list
return length of list
construct an empty list
prepend an item to a list
append an item to a list.

Have experience writing programs for the list operations mentioned above in a functional programming language or in a language with support for the functional paradigm.

For example, in Haskell the list [4, 3, 5] can be written in the form head:tail where head is the first item in the list and tail is the remainder of the list. In the example, we have 4:[3, 5]. We call 4 the head of the list and [3, 5] the tail.

[] is the empty list.

Previous
4.11 Big Data

Next
4.13 Systematic approach to problem solving