Exercise Set 2

1. Write an equational definition of function smallest, where smallest(x) is the smallest member of list x. Assume that the parameter x cannot be the empty list.

2. Write an equational definition of function equal, where equal(x,y) is true if x and y are the same list, and is false if x and y are different lists. Use operator == to compare the members of the lists for equality.

3. Given the definition

   f(0) = 0

   f(n+1) = n*n + f(n)

   show an inside-out evaluation of expression f(3).

4. Given the definition

   g([], k) = k

   g(h::t, k) = g(t, h) when h > k

   g(h::t, k) = g(t, k) when h <= k

   show an inside-out evaluation of expression g([2,5,3,4],4).

5. Choosing from the functions lfold, rfold, map and select, write definitions of each of the following without using loops or recursion.

   1. Write a definition of flatten, where flatten([a,b,c]) = a++b++c. In general, flatten concatenates together the members of a list. So, for example, flatten([2,4], [], [6], [1,9,2]) = [2,4,6,1,9,2].

   2. Write a definition of a function called upper, where upper takes a string and replaces each lower case letter by the equivalent upper case letter. For example, upper("The Quick Brown Fox") = "THE QUICK BROWN FOX". You may use a function called toupper that converts a character to upper case. For example, toupper('a') = 'A', toupper('B') = 'B' and toupper(';') = ';'.

   3. Write a definition of firstGreater where firstGreater(x,k) returns the first member of list x that is greater than k. Presume that such a member exists.

6. What is one important advantage of functional programming languages over imperative languages?