and Functional Programming

Chapter 4

**1 September 2018**

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

Professor of Computer and Information Science

University of Mississippi

211 Weir Hall

P.O. Box 1848

University, MS 38677

(662) 915-5358

Professor of Computer and Information Science

University of Mississippi

211 Weir Hall

P.O. Box 1848

University, MS 38677

(662) 915-5358

**Browser Advisory:** The HTML version of this textbook requires a browser that supports the display of MathML. A good choice as of September 2018 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 10 on Software Testing,

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:

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*`=`

bodywhere

*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`

expression2where

*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:

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

we can write it as

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:

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:

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:

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*:

The list expression `[1..n]`

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

and ending with `n`

. We study lists in a later chapter.

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 10 discusses testing of the Factorial module designed in this chapter. The test script is `TestFactorial.hs`

.

See the Glasgow Haskell Compiler Users Guide 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 of the User Guide 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.

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`

.Inquire about the type of

`fact1`

.Apply function

`fact1`

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

range.Apply functions

`fact2`

,`fact3`

,`fact4`

, and`fact5`

to 7.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.Apply functions

`fact4`

and`fact4'`

to -1. They quickly return with an error.Apply function

`fact5`

to -1. It returns a 1 because it is defined for negative integers.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.Exit GHCi.

Suppose we had set the environment variable `EDITOR`

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

):

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.

Or we could also use a `:set`

command to set the editor within GHCi.

See the Glasgow Haskell Compiler Users Guide for more information about use of GHC and GHCi.

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

In the next chapter, we continue our exploration of Haskell by examining its built-in types.

Reimplement functions

`fact4`

and`fact5`

with type`Integer`

instead of`Int`

. 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* [Cunningham 2014] 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 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.

- [Bird 1988]:
- Richard Bird and Philip Wadler.
*Introduction to Functional Programming*, First Edition, Prentice Hall, 1988. - [Bird 1998]:
- Richard Bird.
*Introduction to Functional Programming using Haskell*, Second Edition, Prentice Hall, 1998. - [Bird 2015]:
- Richard Bird.
*Thinking Functionally with Haskell*, Second Edition, Cambridge University Press, 2015. - [Chiusano 2015]]
- Paul Chiusano and Runar Bjarnason,
*Functional Programming in Scala*, Manning, 2015. - [Cunningham 2014]:
- H. Conrad Cunningham.
*Notes on Functional Programming with Haskell*, 1993-2014. - [Thompson 1996]:
- Simon Thompson.
*Haskell: The Craft of Programming*, First Edition, Addison Wesley, 1996; Second Edition, 1999; Third Edition, Pearson, 2011.

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

, `if`

, guards, basic types (`Int`

, `Integer`

, `Bool`

, `Char`

, functions, tuples, lists, `String`

), `type`

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

commands and use.