Introduction to Functional Programming - List Construction and Deconstruction¶
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:
Note that:
- 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 syntax, 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:
[2,3,5,7,11,13,17,19]
Since JavaScript does not come with a built-in immutable list data structure, we
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:
fp.hd(list)
Lists can be constructed using the cons
function, which takes two
arguments: a single element and a list of elements. The cons
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
in node:
> fp.cons( 5, [1,2,3] )
[ 5, 1, 2, 3 ]
> fp.cons( 1, [ ] )
[ 1 ]
The 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 fp.cons
function.
2. FP - Deconstructing Lists with fp.hd and fp.tl¶
So far, we can build lists using the fp.cons
and fp.makeList
constructors. However, we also need to be able to access the elements of
a list.
The 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 cons
constructor
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.hd
, fp.tl
, and
fp.cons
functions. Note that this problem is randomized. You must
solve it correctly three times in a row to earn the point associated
with it.
3. FP - Deconstructing Lists with fp.hd and fp.tl (2)¶
This problem once more helps you review the semantics of the fp.hd
,
fp.tl
, and fp.cons
functions.
4. FP - fp.isNull, fp.isEq, fp.isZero¶
To check whether a list is empty or not, you must use the
’isNull
’ function:
> fp.isNull( [ ] ) // we say that a list is null when it is equal to [ ]
true
> fp.isNull( [1,2,3] )
false
The isNull
function is a predicate, that is, a function that
returns a Boolean value, true
or false
.
A second predicate that will be useful is ’isEq
’:
> fp.isEq(1,1)
true
> fp.isEq(1,2)
false
A third useful predicate is ’isZero
’:
> fp.isZero(0)
true
> fp.isZero(1)
false
The final problem in this section deals with the syntax and semantics of the fp.hd
,
fp.tl
, and fp.isEq
functions.