Fundamentals of functional programming

The functional programming paradigm

A programming paradigm is a method of programming. The functional programming paradigm is an example of a declarative programming language where all algorithms call functions. This means that the lines of code look and behave like mathematical functions, requiring an input and producing an output. A value is produced for each function call. The idea is that there is one main function, which in turn calls further functions in order to achieve a specific task. Each function may call another function, or call itself recursively in order to generate a result.

The concept is that where a function is being used, it will always return the same value if it is given the same input so there can be no unforeseen side effects. One of these problems with procedural programming languages is that the value of a variable can change throughout the program and that changes made to the value in one subroutine may have an impact within another subroutine.

The motives behind the using functional programming paradigm include:

• Programming requirements may be better defined as a series of abstractions based on functions rather than a more complex series of steps.
• Broader abstractions can lead to fewer errors during implementation.
• Functions can be applied at any level of data abstraction making them highly reusable within a program.
• Functional code is easier to test and debug as each function cannot have any side effects, so only needs testing once.
• There are no concurrency issues as no data is modified by two threads at the same time.
• In multi-processor environments the sequence that functions are evaluated in is not critical.

As functional programs use mathematical expressions they lead themselves to writing applications that require lots of calculations. There are some languages that specifically use the functional programming paradigm such as:

• Lisp
• Haskell
• Standard ML
• Scheme
• Erlang

Other languages provide support for functional programming including:

• Python
• Perl
• C#
• D
• F#
• Java 8
• Delphi XE

The Basics

https://www.youtube.com/watch?v=smOIslkaFa0&index=170&list=PLCiOXwirraUDUYF_qDYcZV8Hce8dsE_Ho

A function type refers to the way in which the expression is created. All functions are of the type A → B where it is defined with an argument type (A) and a result type (B). For example, A is the set that contains {1, 2, 3, 4, 5} and B is the set that contains {1, 4, 9, 16, 25}.

Domain is the set of data of the same type which are the inputs of a function.

Co-domain is the set of values from which the outputs of a function must be drawn.

A is also called the domain and contains objects within a particular data type, in this case integers. B is called the co-domain and is the set from which the output values are chosen.

In functional programming, a value that is passed to a function is known as an argument. For example, in the expression a = f(x) and b = f(2, 4), x, 2 and 4 are arguments.

First-class objects

Within a functional programming environment, a function is a first-class object. A broad definition of a first-class object is any object that can be passed as an argument to or can be returned by a function. In functional programming, this means that a function can be passed as an argument to another function or can be returned from a function as the result. Other objects, such as integer values which can be passed as arguments to a function, are also first-class objects.

High order functions

A function which can accept another function as an argument is known as a higher order function, the three most common of which are map, fold and filter. As an example of a first-class object, in Haskell you might write the function:

map (*2) [1, 2, 3, 4, 5]

map is a function, which takes another function and applies it to every element in a list. *2 (multiply by two) is the function that map is taking in. [1, 2, 3, 4, 5, 6] is the list on which the function is applied.

The result of this higher order function would be [2, 4, 6, 8, 10]

In this example, map is a higher order function and *2, 1, 2, 3, 4 and 5 are all first-class objects.

Application of Function

https://www.youtube.com/watch?v=pke7G2a_hfk&list=PLCiOXwirraUDUYF_qDYcZV8Hce8dsE_Ho&index=171

Function application

The process of providing the function with its inputs is known as function application. With our earlier example we had the function f(x) = x² and the two sets - the domain and co-domain. Set A (the domain) contained the inputs, which were all integers and set B (the co-domain) contained the outputs, also integers.

We input a single value from A, which can be described as the function taking its argument, or the argument being passed to the function. The function is then applied to the argument, which in this case means it squares it, to produced an output B.

Partial function application

It is possible to pass any number of arguments into a function. Where this is the case partial function application can be used to fix the number of arguments that will be passed. The idea of this is that when you have one function that takes lots of arguments, by partially applying the function you effectively create a new function that performs just part of the calculation. The partial application of a function can produce results that are useful in their own rights in addition to the full application of the function.

For example, consider the two notations for a function that adds two integers together by taking two arguments: add: int x int → int add: int → int → int

• The first is a full application of the function which takes two integers as arguments and adds them together to create a result that is also an integer. Both values are passed as arguments at the same time.
• The second is a partial application that shows a new function being created, which always adds the first argument value onto a number. This new function is then applied to the second argument to produce the overall result.

Function composition

Function composition is the process of creating a new function by combining two existing functions together. This is one of the key principles of functional programming as the concept is to have complex functions that in turn are made up of simpler functions. As each component function produces its result, this is passed as an argument result to the calling function. This process continues for each of the component functions until a result is produced for the complex function as a whole.

https://www.youtube.com/watch?v=kLh4cxvI290&list=PLCiOXwirraUDUYF_qDYcZV8Hce8dsE_Ho&index=172

Writing Programs

https://www.youtube.com/watch?v=R2TYsEINXdQ&index=174&list=PLCiOXwirraUDUYF_qDYcZV8Hce8dsE_Ho

TRC Video

https://www.youtube.com/watch?v=4JTp9wx1T20

The map function

The map function applies a given function to every element within a list and returns a corresponding list of results. It is called a map function because it maps one element of the input list (e.g. List1) to the corresponding element in the output list (List2). The function it performs could be anything.

The filter function

The filter function processes a list and then creates a new list that contains elements that match certain criteria. The operation is very similar to a search.

In order to create a filtered list, some kind of selection criteria needs to be applied to the list. This is sometimes called a predicate function and returns a Boolean value of either TRUE or FALSE. For example, a list could be filtered to include all values over 50, or all odd numbers. The way in which the statement is actually written depends on the programming language being used. Typical examples would be If, select, Remove_if, list.filter and where statements.

For example, we might use the function odd to filter odd numbers in a list (List1) into a new list (List2).

The reduce or fold function

The reduce or fold function takes a list of values and reduces it to a single value. This is a recursive process as the function keeps processing until the list is empty. For example, if you took a simple example where you wanted to add the items of a list together, you could reduce the list until you ended up with just one item in it. Let's assume the numbers are from 1 to 5 are in the list.

Instructions	Original list	Apply function (add)	Result
Start with a list	[1, 2, 3, 4, 5]
Take the first item out of the original list and apply the function	[2, 3, 4, 5]	1	1
Recurse	[3, 4, 5]	2 + 1	3
Recurse	[4, 5]	3 + 3	6
Recurse	[5]	4 + 6	10
Recurse	[empty]	5 + 10	15
List is now empty so the function will not recurse any longer

List processing

A list is a set of data items of the same type stored using a single identifier. It is made up of any number of elements and can contain any type of numeric or text strings. The only rule is that you cannot mix data types within a list. You can carry out operations on lists of data, which is more is much more efficient than trying to carry out operations on individual data items.

List components	Explanation
Identifier	The name given to the list.
Data type	Identifies the data type being stored, e.g. text strings, integers, reals. In this case, it is text strings.
Elements	These are the individual values stored in the list. These are identified by their position in the list.
Head	The first element in a list.
Tail	All the other elements in the list apart from the head.
Length	The number of elements in the list. In this case there are eight.

The tail if the list is not just the last item, but all of the items apart from the head. A list can be empty. This may be when it is set up and no data has been entered or it may be after a list has been processed and there is no data left to process. The empty list is often represented as brackets with nothing between them, e.g.[].

Process	Description	Haskell code
Return the head of a list	Identifies the first element in the list	head [1, 2, 3, 4, 5]
Return the tail of a list	Identifies all the other elements apart from the head	tail [1, 2, 3, 4, 5]
Test for an empty list	Checks whether there are any elements in the list	let myList = [3, 4, 5, 2, 7, 3, 4] null myList
Return the length of a list	Identifies how many elements there are in a list	length [5, 6, 7, 2, 3, 5]
Construct an empty list	Creates a list that has no elements in it	let emptyList = []
Prepend an item to a list	Adds an item to the beginning of a list	let setA = [4, 5, 6] let setB = [3] ++ setA
Append an item to a list	Adds an item to the end of a list	let setC = setA ++ [7]

https://www.youtube.com/watch?v=Qs2IhjO1pkM&index=175&list=PLCiOXwirraUDUYF_qDYcZV8Hce8dsE_Ho

Haskell

https://www.youtube.com/watch?v=Qs2IhjO1pkM&index=175&list=PLCiOXwirraUDUYF_qDYcZV8Hce8dsE_Ho