Exploring Languages

with Interpreters

and Functional Programming

Chapter 4

**H. Conrad Cunningham**

**04 April 2022**

Copyright (C) 2016, 2017, 2018, 2022, H. Conrad Cunningham

Professor of Computer and Information Science

University of Mississippi

214 Weir Hall

P.O. Box 1848

University, MS 38677

(662) 915-7396 (dept. office)

Professor of Computer and Information Science

University of Mississippi

214 Weir Hall

P.O. Box 1848

University, MS 38677

(662) 915-7396 (dept. office)

**Browser Advisory:** The HTML version of this textbook
requires a browser that supports the display of MathML. A good choice as
of April 2022 is a recent version of Firefox from Mozilla.

The goals of this chapter are to

introduce the definition of Haskell functions using examples

illustrate the use of the

`ghci`

interactive REPL (Read-Evaluate-Print Loop) interpreter

Let’s look at our first function definition in the Haskell language, a program to implement the factorial function for natural numbers.

The Haskell source file `Factorial.hs`

holds the Haskell
function definitions for this chapter. The test script is in source file
`TestFactorial.hs`

; it is discussed
further in Chapter 12 on
testing of Haskell programs.

We can give two mathematical definitions of factorial, *fact*
and *fact’*, that are equivalent for all natural number
arguments. We can define *fact* using the product operator as
follows:

fact$(n) = \prod_{i=1}^{i=n}\,i$

For example,

fact$(4) = 1 \times 2 \times 3 \times 4$.

By definition

fact$(0) = 1$

which is the *identity* element of the multiplication
operation.

We can also define the factorial function *fact’* with a
*recursive* definition (or *recurrence relation*) as
follows:

fact’$(n) = 1$, if $n = 0$

fact’$(n) = n \times$ fact’$(n-1)$, if $n \geq 1$

Since the domain of *fact’* is the set of natural numbers, a
set over which induction is defined, we can easily see that this
recursive definition is well defined.

For $n = 0$, the base case, the value is simply $1$.

For $n \geq 1$, the value of

*fact’*$(n)$ is recursively defined in terms of*fact’*$(n-1)$. The argument of the recursive application decreases toward the base case.

In the Review of Relevant Mathematics appendix, we prove that
*fact*$(n)$
$=$
*fact’*$(n)$
by mathematical induction.

The Haskell functions defined in the following subsections must
compute
*fact*$(n)$
when applied to argument value
$n \geq 0$.

`fact1`

One way to translate the recursive definition *fact’* into
Haskell is the following:

```
fact1 :: Int -> Int
= if n == 0 then
fact1 n 1
else
* fact1 (n-1) n
```

The first line above is the

*type signature*for function`fact1`

. In general, type signatures have the syntax*object*`::`

*type*.Haskell type names begin with an uppercase letter.

The above defines object

`fact1`

as a function (denoted by the`->`

symbol) that takes one argument of type integer (denoted by the first`Int`

) and returns a value of type integer (denoted by the last`Int`

).Haskell does not have a built-in natural number type. Thus we choose type

`Int`

for the argument and result of`fact1`

.The

`Int`

data type is a bounded integer type, usually the integer data type supported directly by the host processor (e.g., 32- or 64-bits on most current processors), but it is guaranteed to have the range of at least a 30-bit, two’s complement integer ($-2^{29}$ to $2^{29}$).The declaration for the function

`fact1`

begins on the second line. Note that it is an equation of the form*fname parms*`=`

*body*where

*fname*is the function’s name,*parms*are the function’s parameters, and*body*is an expression defining the function’s result.Function and variable names begin with lowercase letters optionally followed by a sequence of characters each of which is a letter, a digit, an apostrophe (

`'`

) (sometimes pronounced “prime”), or an underscore (`_`

).A function may have zero or more parameters. The parameters are listed after the function name without being enclosed in parentheses and without commas separating them.

The parameter names may appear in the

*body*of the function. In the evaluation of a function*application*the actual argument values are substituted for parameters in the*body*.Above we define the

*body*function`fact1`

to be an`if-then-else`

*expression*. This kind of expression has the form`if`

*condition*`then`

*expression1*`else`

*expression2*where

*condition*is a Boolean expression, that is, an expression of Haskell type`Bool`

, which has either`True`

or`False`

as its value*expression1*is the expression that is returned when the condition is`True`

*expression2*is the expression (with the same type as*expression1*) that is returned when the condition is`False`

Evaluation of the

`if-then-else`

expression in`fact1`

yields the value`1`

if argument`n`

has the value`0`

(i.e.,`n == 0`

) and yields the value`n * fact1 (n-1)`

otherwise.The

`else`

clause includes a recursive application of`fact1`

. The whole expression`(n-1)`

is the argument for the recursive application, so we enclose it in parenthesis.The value of the argument for the recursive application is less than the value of the original argument. For each recursive application of

`fact`

to a natural number, the argument’s value thus moves closer to the termination value`0`

.Unlike most conventional languages, the

*indentation is significant*in Haskell. The indentation indicates the nesting of expressions.For example, in

`fact1`

the`n * fact1 (n-1)`

expression is nested inside the`else`

clause of the`if-then-else`

expression.This Haskell function does not match the mathematical definition given above. What is the difference?

Notice the domains of the functions. The evaluation of

`fact1`

will go into an “infinite loop” and eventually abort when it is applied to a negative value.

In Haskell there is *only* one way to form more complex
expressions from simpler ones: *apply* a function.

Neither parentheses nor special operator symbols are used to denote
function application; it is denoted by simply listing the argument
expressions following the function name. For example, a function
`f`

applied to argument expressions `x`

and `y`

is written in the following
*prefix* form:

` f x y`

However, the usual prefix form for a function application is not a
convenient or natural way to write many common expressions. Haskell
provides a helpful bit of syntactic sugar, the *infix*
expression. Thus instead of having to write the addition of `x`

and `y`

as

` add x y`

we can write it as

`+ y x `

as we have since elementary school. Here the symbol `+`

represents
the addition function.

Function application (i.e., juxtaposition of function names and
argument expressions) has higher precedence than other operators. Thus
the expression `f x + y`

is the
same as `(f x) + y`

.

`fact2`

An alternative way to differentiate the two cases in the recursive
definition is to use a different equation for each case. If the Boolean
*guard* (e.g., `n == 0`

)
for an equation evaluates to true, then that equation is used in the
evaluation of the function. A guard is written following the `|`

symbol as
follows:

```
fact2 :: Int -> Int
fact2 n | n == 0 = 1
| otherwise = n * fact2 (n-1)
```

Function `fact2`

is equivalent
to the `fact1`

. Haskell evaluates
the guards in a top-to-bottom order. The `otherwise`

guard always succeeds; thus it’s use above is similar to the trailing
`else`

clause on the `if-then-else`

expression used in `fact1`

.

`fact3`

and
`fact4`

Another equivalent way to differentiate the two cases in the
recursive definition is to use *pattern matching* as follows:

```
fact3 :: Int -> Int
0 = 1
fact3 = n * fact3 (n-1) fact3 n
```

The parameter pattern `0`

in the first *leg* of the
definition only matches arguments with value 0. Since Haskell checks
patterns and guards in a top-to-bottom order, the `n`

pattern
matches all nonzero values. Thus `fact1`

, `fact2`

, and `fact3`

are equivalent.

To stop evaluation from going into an “infinite loop” for negative
arguments, we can remove the negative integers from the function’s
domain. One way to do this is by using guards to narrow the domain to
the natural numbers as in the definition of `fact4`

below:

```
fact4 :: Int -> Int
fact4 n | n == 0 = 1
| n >= 1 = n * fact4 (n-1)
```

Function `fact4`

is undefined
for negative arguments. If `fact4`

is applied to a negative argument, the evaluation of the program
encounters an error quickly and returns without going into an infinite
loop. It prints an error and halts further evaluation.

We can define our own error message for the negative case using an
`error`

call as in `fact4'`

below.

```
fact4' :: Int -> Int
fact4' n | n == 0 = 1
| n >= 1 = n * fact4' (n-1)
| otherwise = error "fact4' called with negative argument"
```

In addition to displaying the custom error message, this also displays a stack trace of the active function calls.

`fact5`

The four definitions we have looked at so far use recursive patterns
similar to the recurrence relation *fact’*. Another alternative
is to use the library function `product`

and the
list-generating expression `[1..n]`

to define a solution that is like the function *fact*:

```
fact5 :: Int -> Int
= product [1..n] fact5 n
```

The list expression `[1..n]`

generates a *list* of consecutive integers beginning with
`1`

and ending with `n`

. We study lists beginning with
Chapter 13.

The library function `product`

computes the product of the elements of a finite list.

If we apply `fact5`

to a
negative argument, the expression `[1..n]`

generates an empty
list. Applying `product`

to
this empty list yields 1, which is the identity element for
multiplication. Defining `fact5`

to return 1 is consistent with the function *fact* upon which it
is based.

Which of the above definitions for the factorial function is better?

Most people in the functional programming community would consider
`fact4`

(or `fact4'`

) and `fact5`

as being better than the others.
The choice between them depends upon whether we want to trap the
application to negative numbers as an error or to return the value
1.

Chapter 12 discusses testing
of the Factorial module designed in this chapter. The test script is `TestFactorial.hs`

.

See the Glasgow Haskell Compiler Users Guide [2] for information on the Glasgow Haskell Compiler (GHC) and its use.

GHCi is an environment for using GHC interactively. That is, it is a REPL (Read-Evaluate-Print-Loop) command line interface using Haskell. The “Using GHCi” chapter [3] of the GHC User Guide [2] describes its usage.

Below, we show a GHCi session where we load source code file (module)
`Factorial.hs`

and apply the factorial functions to various inputs. The instructor ran
this in a Terminal session on an iMac running macOS 10.13.4 (High
Sierra) with `ghc`

8.4.3
installed.

Start the REPL.

`bash-3.2$ ghci GHCi, version 8.4.3: http://www.haskell.org/ghc/ :? for help`

Load module

`Fact`

that holds the factorial function definitions. This assumes the`Factorial.hs`

file is in the current directory. The`load`

command can be abbreviated as just`:l`

.`Prelude> :load Factorial 1 of 1] Compiling Factorial ( Factorial.hs, interpreted ) [Ok, one module loaded.`

Inquire about the type of

`fact1`

.`*Factorial> :type fact1 fact1 :: Int -> Int`

Apply function

`fact1`

to 7, 0, 20, and 21. Note that the factorial of 21 exceeds the`Int`

range.`*Factorial> fact1 7 5040 *Factorial> fact1 0 1 *Factorial> fact1 20 2432902008176640000 *Factorial> fact1 21 -4249290049419214848`

Apply functions

`fact2`

,`fact3`

,`fact4`

, and`fact5`

to 7.`*Factorial> fact2 7 5040 *Factorial> fact3 7 5040 *Factorial> fact4 7 5040 *Factorial> fact5 7 5040`

Apply functions

`fact1`

,`fact2`

, and`fact3`

to -1. All go into an infinite recursion, eventually terminating with an error when the runtime stack overflows its allocated space.`*Factorial> fact1 (-1) *** Exception: stack overflow *Factorial> fact2 (-1) *Factorial> fact3 (-1) *** Exception: stack overflow`

Apply functions

`fact4`

and`fact4'`

to -1. They quickly return with an error.`*Factorial> fact4 (-1) *** Exception: Factorial.hs:(54,1)-(56,29): Non-exhaustive patterns in function fact4 *Factorial> fact4' (-1) *** Exception: fact4' called with negative argument CallStack (from HasCallStack): error, called at Factorial.hs:64:17 in main:Factorial`

Apply function

`fact5`

to -1. It returns a 1 because it is defined for negative integers.`*Factorial> fact5 (-1) 1`

Set the

`+s`

option to get information about the time and space required and the`+t`

option to get the type of the returned value.`*Factorial> :set +s *Factorial> fact1 20 2432902008176640000 0.00 secs, 80,712 bytes) (*Factorial> :set +t *Factorial> fact1 20 2432902008176640000 it :: Int 0.05 secs, 80,792 bytes) (*Factorial> :unset +s +t *Factorial> fact1 20 2432902008176640000`

Exit GHCi.

`:quit Leaving GHCi.`

Suppose we had set the environment variable `EDITOR`

to our
favorite text editor in the Terminal window. For example, on a MacOS
system, your instructor might give the following command in shell (or in
a startup script such as `.bash_profile`

):

`export EDITOR=Aquamacs `

Then the `:edit`

command within GHCi allows us to edit the
source code. We can give a filename or default to the last file
loaded.

`:edit `

Or we could also use a `:set`

command to set the editor
within GHCi.

```
:set editor Aquamacs
...
:edit
```

See the Glasgow Haskell Compiler (GHC) User’s Guide [2] for more information about use of GHC and GHCi.

In this chapter (4), we looked at our first Haskell functions and how to execute them using the Haskell interpreter.

In Chapter 5, we continue our exploration of Haskell by examining its built-in types.

The Haskell source module `Factorial.hs`

gives the factorial
functions used in this chapter. The test script in source file `TestFactorial.hs`

is discussed further
in Chapter 12 on testing of
Haskell programs.

Reimplement functions

`fact4`

and`fact5`

with type`Integer`

instead of`Int`

.`Integer`

is an unbounded precision integer type (discussed in the next chapter). Using`ghci`

, execute these functions for values -1, 7, 20, 21, and 50 using`ghci`

.Develop both recursive and iterative (looping) versions of a factorial fuunction in an imperative language (e.g., Java, C++, Python 3, etc.)

In Summer 2016, I adapted and revised much of this work in from
Chapter 3 of my *Notes on Functional Programming with Haskell*
[1] and
incorporated it into Chapter 2, Basic Haskell Functional Programming, of
my 2017 Haskell-based programming languages textbook.

In Spring and Summer 2018, I divided the previous Basic Haskell
Functional Programming chapter into four chapters in the 2018 version of
the textbook, now titled *Exploring Languages with Interpreters and
Functional Programming.* Previous sections 2.1-2.3 became the basis
for new Chapter 4, First Haskell Programs (this chapter); previous
Section 2.4 became Section 5.3 in the new Chapter 5, Types; and previous
sections 2.5-2.7 were reorganized into new Chapter 6, Procedural
Abstraction, and Chapter 7, Data Abstraction.

I retired from the full-time faculty in May 2019. As one of my post-retirement projects, I am continuing work on this textbook. In January 2022, I began refining the existing content, integrating additional separately developed materials, reformatting the document (e.g., using CSS), constructing a bibliography (e.g., using citeproc), and improving the build workflow and use of Pandoc.

I maintain this chapter as text in Pandoc’s dialect of Markdown using embedded LaTeX markup for the mathematical formulas and then translate the document to HTML, PDF, and other forms as needed.

TODO: Update

Factorials, function definition and application, recursion, function
domains, `error`

, `if`

, guards,
basic types (`Int`

, `Integer`

, `Bool`

, library
(Prelude) functions, REPL, `ghci`

commands and use.

[1]

H.
Conrad Cunningham. 2014. *Notes on functional programming with
Haskell*. University of Mississippi, Department of
Computer and Information Science, University, Mississippi,
USA. Retrieved from https://john.cs.olemiss.edu/~hcc/docs/Notes_FP_Haskell/Notes_on_Functional_Programming_with_Haskell.pdf

[2]

Haskell Organization. 2022. Glasgow
Haskell Compiler (GHC) user’s guide. Retrieved from https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/

[3]

Haskell Organization. 2022. Using
GHCi: Chapter 3, GHC user’s guide. Retrieved
from https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/ghci.html