Discrete math with computers_3

284	CHAPTER 11. FUNCTIONS

Example 110. The argument type of the following function is Integer, but its domain is the set of non-negative integers. Suppose that it would be a runtime error to evaluate an application of f to a negative number, but suppose also that we would like an informative error message if this happens. The error function can be used to terminate the execution with a tailor-made message. A common technique, illustrated here, is to construct the error message string, including pertinent information about the argument. In this case, we simply convert x to a string, with show x, and include that in the message.

f :: Integer -> Integer f x =

if x >= 0 then 10*x

else error ("f was applied to a negative number " ++ show x ++ ". Don’t do it again!")

Here are the results of evaluating two applications of f. The argument is in the domain of f in the first application, but not in the second.

>f (2+2)

40

>f (2-5)

Program error: f was applied to a negative number -3. Don’t do it again!

Unfortunately, it is not possible to detect all errors at runtime, and when an undetectable error occurs it is impossible to print a useful error message. Sometimes a recursive function goes into an infinite loop, and there is simply no output at all.

Example 111. The infinite loop function takes an argument and calls itself with the same argument. Because it makes no progress toward a termination condition, any application of this function will run forever. The user must interrupt the execution, typically by typing CTRL-C or by clicking on Stop.

infinite_loop :: a -> a infinite_loop x = infinite_loop x

An application of a total function will always terminate and produce a result. There are three possible outcomes from evaluating an application of a partial function to an argument: the application could terminate with a result; it could produce a runtime error message; or it could go into an infinite loop. For example, the following function will terminate if its argument is even, but it will go into an infinite loop if the argument is odd:

haltIfEven x = if even x

11.4. TOTAL AND PARTIAL FUNCTIONS

285

then x

else infinite_loop x

If we try applying haltIfEven to some arguments, we might quickly discover that haltIfEven 6 6. However, when we attempt to evaluate the expression haltIfEven 7 there will not be any output at all; the computation will just go on and on. When a computer is running a program but not producing any output, it would be useful to know whether it just needs more time, or whether it is stuck in an infinite loop. For this particular example it is obvious when the function will terminate and when it will loop forever, but what about more complicated functions where this is not obvious?

It would be extremely useful to have a function called wouldHalt that takes an arbitrary function f and an argument value x, and that returns True if and only if f would halt if we actually evaluate f x:

wouldHalt :: (Integer->Integer) -> Integer -> Bool

This is called the Halting Problem.

Obviously we cannot implement wouldHalt by actually evaluating f. Suppose we write it something like this:

wouldHalt :: (Integer->Integer) -> Integer -> Bool wouldHalt f x =

if f x == f x then True else False

The problem is that if f x goes into an infinite loop, then wouldHalt will never get the opportunity to return False. It will always return True if the result should be True, but it will go into an infinite loop if the result should be False.

Since wouldHalt cannot actually evaluate f x, it must instead analyse the definition of f, somehow figure out how it works, and then decide whether f x would halt. We could easily define a simplified wouldHalt that can handle haltIfEven and similar functions. Could we extend it, with enough e ort, so that our function solves the Halting Problem? Unfortunately this is impossible:

Theorem 76. There does not exist a function wouldHalt such that for all f and x,

True, if f x terminates

wouldHalt f x =

False, if f x does not terminate

Proof. Define the function paradox as follows:

paradox :: Integer -> Integer paradox x =

if wouldHalt paradox x then paradox x

else 1

286	CHAPTER 11. FUNCTIONS

Now consider the expression paradox x. One of the following two cases must hold:

• Suppose paradox x halts and produces a result. Then

wouldHalt paradox x True;

therefore the definition reduces to paradox x = paradox x, so paradox x does not halt. This is a contradiction; therefore it is impossible that paradox x halts.

• Suppose paradox x does not halt. Then

wouldHalt paradox x False.

The definition then simplifies to paradox x = 1, and it halts.

To summarise, if paradox x halts then it does not halt, and if it does not halt then it halts! There is no possibility which avoids contradiction. Therefore the function wouldHalt does not exist.

The proof that the Halting Problem is unsolvable was discovered in the 1930s by Alan Turing. This is one of the earliest and most important results of computability theory. One of the commonest methods for proving that a function does not exist is to show how it could be used to solve the Halting Problem, which is unsolvable. This theorem also has major practical implications: it means that some software tools that would be very useful cannot actually be implemented.

A consequence of the unsolvability of the Halting Problem is that it is impossible to write a Haskell function that determines whether another Haskell function is total or partial. However, we can introduce data structures to represent the graphs of partial functions, with an explicit value that represents. The software tools file takes this approach, as described below.

The definition of a function requires that every element of the domain be mapped to some element of the result type, which can be the undefined value. This means that we need to use a new type to represent the result returned by a function, called FunVals. This type has two kinds of element. The first is Undefined, which means that the result value is . The other is called Value, and takes an argument that is the actual value returned by the function.

Now we can define a predicate that returns True if its argument is a partial function (in other words if some member of its result type is undefined), and False otherwise:

isPartialFunction

:: (Eq a, Show a, Eq b, Show b)

=> Set a -> Set b -> Set (a,FunVals b) -> Bool

11.5. FUNCTION COMPOSITION

287

There is also a function isFun that takes a relation, and determines whether the relation is also a function:

isFun :: (Eq a, Show a, Eq b, Show b) =>

Set a -> Set b -> Set (a,FunVals b) -> Bool

Exercise 1. Decide whether the following functions are partial or total, and then run the tests on the computer:

(a)isPartialFunction [1,2,3] [2,3]

[(1,Value 2),(2,Value 3),(3,Undefined)]

(b)isPartialFunction

[1,2] [2,3]

[(1,Value 2),(2,Value 3)]

Exercise 2. Work out the following expressions, by hand and using the computer:

isFun [1,2,3] [1,2] [(1,Value 2),(2,Value 2)] isFun [1,2,3] [1,2] [(1,Value 2),(2,Value 2),

(3,Value 2),(3,Value 1)] isFun [1,2,3] [1,2] [(1,Value 2),

(2,Value 2),(3,Value 2)]

Exercise 3. What is the value of mystery x where mystery is defined as:

mystery :: Int -> Int

mystery x = if mystery x == 2 then 1 else 3

Exercise 4. What is the value of mystery2 x where mystery2 is defined as:

mystery2 :: Int -> Int

mystery2 x = if x == 20 then 2 + mystery2 x else 3

11.5Function Composition

It is often possible to structure a computation as a sequence of function applications organised as a pipeline: the output from one function becomes the input to the next, and so on. In the simplest case, there are just two functions in the pipeline: the input x goes into the first function, g, whose output goes into the second function f (Figure 11.6).

Definition 69. Let g :: a → b and f :: b → c be functions. Then the composition of f with g, written f ◦ g, is a function such that:

(f ◦ g)	::	a → c
(f ◦ g) x	=	f (g x)

288									CHAPTER 11. FUNCTIONS
	x			g				f		y

Figure 11.6: Functional Composition (f ◦ g) x = f (g x)

When you think of composition as a pipeline, the input x goes into the first function g; this produces an intermediate result g x, which is the input to the second function f , and the final result is f (g x). Notice, however, that in the notation f ◦ g, the functions are written in backwards order. This may be unfortunate, but this is the standard definition of function composition, and you need to be familiar with it. Just remember that f ◦ g means first apply g, then f .

The ◦ symbol is an operator that takes two functions and produces a new function, just as + is an operator that takes two numbers and produces a new number. The first argument to ◦ is f :: b → c, and the second argument is g :: a → b, and the entire composition takes an input x :: a and returns a result (f (g x)) :: c. Therefore the ◦ operator has the following type:

(◦) :: (b → c) → (a → b) → (a → c)

Haskell has a built-in operator for function composition. Since ◦ is unfortunately not an ASCII character, the full stop character ‘.’ is used instead to denote function composition.

Definition 70. The Haskell function composition operator is

(.) :: (b -> c) -> (a -> b) -> (a -> c) (f.g) x = f (g x)

Example 112. Suppose that you wish to increment the second elements of a list of pairs called lstpairs. You could write this as

map increment (map snd lstpairs)

but it is often clearer to write it as

map (increment.snd) lstpairs

This helps the reader to see that several operations are going to be applied in turn to each element of the list.

Composition is often used to define a processing pipeline, as shown in Figure 11.6, but we often need more than two functions in the pipeline. Figure 11.7 shows a typical example, where four functions are connected together using ◦. The following theorem states an extremely important property of the ◦ operator, which makes it easier to define such pipelines:

11.5. FUNCTION COMPOSITION

289

Theorem 77. Functional composition (◦) is associative. That is, for all functions h :: a → b, g :: b → c, f :: c → d,

f ◦ (g ◦ h) = (f ◦ g) ◦ h,

and both the leftand right-hand sides of the equation have type a → d.

Proof. We need to prove that the two functions f ◦ (g ◦ h) and (f ◦ g) ◦ h are extensionally equal. To do this we need to choose an arbitrary x :: a, and show that both functions give the same result when applied to x. That is, we need to prove that the following equation holds:

(f ◦ (g ◦ h)) x = ((f ◦ g) ◦ h) x.

This is done by straightforward equational reasoning, repeatedly using the

definition of ◦:

((f ◦ g) ◦ h) x

=(f ◦ g) (h x)

=f (g (h x))

=f ((g ◦ h) x)

=(f ◦ (g ◦ h)) x

The significance of this theorem is that we can consider a complete pipeline as a single black box; there is no need to structure it two functions at a time. Similarly, you can omit the redundant parentheses in the mathematical notation. The following compositions are all identical:

(f1 ◦ f2) ◦ (f3 ◦ f4) f1 ◦ (f2 ◦ (f3 ◦ f4)) ((f1 ◦ f2) ◦ f3) ◦ f4 f1 ◦ ((f2 ◦ f3) ◦ f4) (f1 ◦ (f2 ◦ f3)) ◦ f4

The parentheses in all of these expressions have no e ect on the meaning of the expression, and they make the notation harder to read, so it is customary to omit them and write simply

f1 ◦ f2 ◦ f3 ◦ f4.

Notice, however, that you must put parentheses around an expression denoting a function when you apply it to an argument. For example,

(f1 ◦ f2 ◦ f3 ◦ f4) x

is the correct way to apply the pipeline to the argument x. It would be incorrect to omit the outer parentheses, as in

f1 ◦ f2 ◦ f3 ◦ f4 x,

290	CHAPTER 11. FUNCTIONS

f1

f2

f3

f4

Figure 11.7: A Pipeline Defined via Functional Composition f4 ◦ f3 ◦ f2 ◦ f1

because function application takes precedence over all other operations, and the meaning would be equivalent to

f1 ◦ f2 ◦ f3 ◦ (f4 x),

which is not what was intended. In functional programming it is common to see a pipeline of functions connected with the ◦ operator (written as ‘.’ in Haskell); if this expression is applied to an argument, then there is just one pair of parentheses around the whole pipeline, but otherwise no parentheses are needed. For example, here are two Haskell equations, defining a function g and a data value y:

g = f1 . f2 . f3 . f4

y = (f1 . f2 . f3 . f4) x

The software tools contain an implementation of the following function; its two arguments are functions represented as graphs, and it returns the composition, also represented as a graph.

functionalComposition

:: (Eq a, Show a, Eq b, Show b, Eq c, Show c) => Set (a,FunVals b) -> Set (b,FunVals c)

-> Set (a,FunVals c)

Exercise 5. Work out the values of the following expressions, and then check your result by evaluating them with the computer:

map (increment.increment.increment) [1,2,3] map ((+ 2).(* 2)) [1,2,3]

Exercise 6. Using the definitions below, work out the type and graph of f.g, and check using the computer.

f : Int -> String f 1 = "cat"

f 2 = "dog" f 3 = "mouse"

g : Char -> Int g ’a’ = 1

11.6. PROPERTIES OF FUNCTIONS

291

g ’b’ = 2 g ’c’ = 2 g ’d’ = 3

Exercise 7. Functions are often composed with each other in order to form a pipeline that processes some data. What does the following expression do?

((map (+ 1)).(map snd)) xs

Exercise 8. Sometimes access to deeply nested constructor expressions is performed by function composition. What is the value of this expression?

(fst.snd.fst) ((1,(2,3)),4).

11.6Properties of Functions

We have used four sets to characterise a function: the argument type, the domain, the result type, and the image. There are several useful properties of functions that concern these four sets, and we will examine them in this section.

11.6.1Surjective Functions

A surjective function has an image that is the same as its result type (sometimes called the range). Thus the function can, given suitable input, produce any of the elements of the result type.

Definition 71. A function f :: A → B is surjective if

b B. ( a A. f a = b).

Example 113. The function even :: Integer -> Bool has a result type with only two elements, True and False. Both of these values are in the function’s image, as demonstrated by the applications even 2 = True and even 3 = False. Therefore every element of the result type is also an element of the image, and even is surjective.

Example 114. The times two function takes an integer and doubles it:

times_two :: Int -> Int times_two n = 2 * n

The image of the function is the set of even integers; this is a proper subset of the result type, so times two is not surjective.

292			CHAPTER 11. FUNCTIONS
Surjective		Non-surjective
functions		functions
1	4	1	4
2	5	2	5
3	6	3	6
1	4	1	4
2		2	5
3	6	3	6

Figure 11.8: Two Surjective Functions and Two That Are Not Surjective

Example 115. The increment function takes an integer argument and adds 1 to it. The result type is Integer, and the image is also Integer, because every integer is 1 greater than its predecessor. Thus the image set is the same as the result type, and the function is surjective.

Example 116. Let A = {1, 2, 3} and B = {4, 5}. Define f :: A → B as {(1, 4), (2, 5), (3, 4)}. Then f is surjective, because there is an ordered pair whose second component is 4, and the same is also true of 5.

Example 117. Figure 11.8 shows two surjective functions and two that are not surjective. The domain and image of each function is circled.

If the result type of a function is larger than its domain, then the function cannot be surjective.

Example 118. Let A = {2, 3} and B = {4, 5, 6}. If f :: A → B then it is not surjective, since it is not possible for it to contain three ordered pairs (x1, 4), (x2, 5) and (x3, 6) such that x1, x2 and x3 are all elements of A and are all distinct.

Example 119. The following Haskell functions are surjective:

not :: Bool -> Bool member v :: [Int] -> Bool increment :: Int -> Int id :: a -> a

All of these functions have result types that are no larger than their domain types.

11.6. PROPERTIES OF FUNCTIONS

293

Example 120. The following Haskell functions are not surjective. The length function returns only zero or a positive integer, and abs returns the absolute value of its argument, so both functions can never return a negative number. The times two function may be applied to an odd or an even number, but it always returns an even result.

length :: [a] -> Int abs :: Int -> Int times_two :: Int -> Int

The software tools file defines the following function, which takes a graph representation of a function and determines whether it is surjective:

isSurjective

:: (Eq a, Show a, Eq b, Show b)

=> Set a -> Set b -> Set (a,FunVals b) -> Bool

Exercise 9. Decide whether the functions represented by the graphs in the following examples are surjective, and then check using the computer:

isSurjective [1,2,3] [4,5]

[(1, Value 4), (2, Value 5), (3, Value 4)]

isSurjective [1,2,3] [4,5]

[(1, Value 4), (2, Value 4), (3, Value 4)]

Exercise 10. Which of the following functions are surjective?

(a)f :: A → B, where A = {1, 2}, B = {2, 3, 4} and f = {(1, 2), (2, 3)}.

(b)g :: C → D, where C = {1, 2, 3}, D = {1, 2} and g = {(1, 1), (2, 1), (3, 2)}.

Exercise 11. Which of the following functions are not surjective, and why?

(a)map increment :: [Int] -> [Int]

(b)take 0 :: [a] -> [a]

(c)drop 0 :: [a] -> [a]

(d)(++) xs :: [a] -> [a]

11.6.2Injective Functions

The essential requirement that a relation must satisfy in order to be a function is that it maps each element of its domain to exactly one element of the image. An injective function has a similar property: each element of the image is the result of applying the function to exactly one element of the domain.