4.2.1 Factorial function specification

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$.

4.2.2 Factorial function using if-then-else: fact1

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

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

• 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

    x + y

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.

4.2.3 Factorial function using guards: 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.

4.2.4 Factorial function using pattern matching: 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 
    fact3 0 = 1 
    fact3 n = n * fact3 (n-1)

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.

4.2.5 Factorial function using built-in library function: 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 
    fact5 n = product [1..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.

4.2.6 Testing

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