2.1. Introduction to Functional Programming - List Construction and Deconstruction¶
2.1.1. FP - Constructing Lists with cons¶
Functional programming (FP) is a programming paradigm where functions are the main abstraction and in which functions are pure, first-class values and data is immutable.
A function is pure if it returns a value without having any side effects. A pure function does not affect any data outside of itself (no assignment statements, no I/O) and does not access any global data that could be changed by other functions. A pure function ALWAYS returns the same value given the same input, like in mathematics. In fact, FP started with Alonzo Church’s \(\lambda\)-calculus, which we will study later in this course.
First-class values, like integers, booleans, strings, etc., are values that can be assigned to variables, can be stored in arrays and other data structures, can be used as an argument in a function call and can be the return value of a function call. In FP, functions are first-class values. Functions that take one or more functions as parameters and/or return a function are called higher-order functions (much, much more on this later).
In FP, all data items are immutable: once a value is created, it can never be modified. Even in Java, which is an OO language, not a FP language, String objects are immutable.
The most basic, built-in data structure in FP languages is the list, whose structure can be described in BNF notation as follows:
- We are limiting ourselves to lists of integers for now, and
- The grammar above describes the abstract syntax or structure of lists, not its concrete structure, that is, how lists actually appear in any particular FP language.
For our functional programming module, the concrete syntax of lists will use square brackets around each list and a comma between pairs of consecutive elements in the list.
So, the empty list will be represented by:
and non-empty lists will look like this:
provide one as part of a module called
fp.js, which is used throughout Chapter 2.
You can make this module available in your JS files by including the following line at the top of the file:
var fp = require('./fp');
Then, every time you want to use any of the functions defined in this
module (such as the
hd function to be described shortly), you will
prepend the prefix
fp. to the function’s name. For example, you
would call the
hd function with the argument
list like this:
Lists can be constructed using the
cons function, which takes two
arguments: a single element and a list of elements. The
function returns a new list equal to its second argument but with its
first argument inserted in front. So, in a read-eval-print loop such as that provided
> fp.cons( 5, [1,2,3] ) [ 5, 1, 2, 3 ] > fp.cons( 1, [ ] ) [ 1 ]
fp module provides a helper function to create an arbitrarily
long list in one call, like this:
> fp.makeList(1,2,3) [ 1, 2, 3 ] > fp.makeList(1,2,3,4,5,6,7,8,9,10) [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] > fp.makeList() 
The following problem deals with the syntax and semantics of the
2.1.2. FP - Deconstructing Lists with fp.hd and fp.tl¶
So far, we can build lists using the
constructors. However, we also need to be able to access the elements of
fp module provides the so-called “head” and “tail” accessors.
fp.hd(l)returns the first element of its list argument.
fp.tl(l)returns the list obtained by removing the head from its list argument.
> fp.hd([1,2,3]) 1 > fp.tl([1,2,3]) // how would you access the second or third element of this list? [ 2, 3 ] > fp.hd() Error: hd can only be called with a non-empty list. > fp.tl() Error: tl can only be called with a non-empty list.
In languages like Lisp and Scheme, these accessors are called “car” and “cdr” respectively.
It is important to note the symmetry between the
and the list accessors:
cons builds a list using the same building
blocks that the accessors return.
This problem deals with the semantics of the
fp.cons functions. Note that this problem is randomized. You must
solve it correctly three times in a row to earn the point associated
2.1.3. FP - Deconstructing Lists with fp.hd and fp.tl (2)¶
This problem once more helps you review the semantics of the
2.1.4. FP - fp.isNull, fp.isEq, fp.isZero¶
To check whether a list is empty or not, you must use the
> fp.isNull( [ ] ) // we say that a list is null when it is equal to [ ] true > fp.isNull( [1,2,3] ) false
isNull function is a predicate, that is, a function that
returns a Boolean value,
A second predicate that will be useful is ’
> fp.isEq(1,1) true > fp.isEq(1,2) false
A third useful predicate is ’
> fp.isZero(0) true > fp.isZero(1) false
The final problem in this section deals with the syntax and semantics of the