CSCI 6220
Practice questions for exam

Use Haskell syntax for writing function definitions. Include a type for each function.

1. Write a definition of a function power(x,n) that computes xⁿ. Assume that n is a positive integer.

2. Write another definition of power, but this time use only tail recursion. You can use a helper function.

3. Write a definition of function odds(x) that uses a list comprehension to produce the members of list x that are odd numbers. Assume x is a list of ints.

4. If x = [x₁,...,x_n] and y = [y₁,...,y_n] are two lists of real numbers of equal length, define the inner product of x and y to be the real number x₁*y₁ + ... + x_n*y_n. Write a function ip(x,y) that produces the inner product of lists x and y. This function is only required to work when the two lists have equal length.

5. Write a definition of function numwords that tells the number of words in a string. By definition, words are separated by spaces. Do not consider any other kind of separator. However, several spaces in a row are equivalent to a single space, and act to separate two words. A word must contain at least one non-space character.

6. Suppose that f(x) = (a,b) produces an ordered pair, and that g is another function. Say that the scrunch of f and g is the function h defined by h(x) = (g(a),b). That is, h runs f, and only passes the left-hand member of the pair produced by f to g. Write a definition of scrunch(f,g).

7. Suppose that f is defined by

        f x y = y x
     

   What kind of thing is f(4)? (Is it a number, a list, a function, or something else?)

8. Using the definitions of map and ++, show by induction that, for every list, map f (x++y) = map f x ++ map f y. The definition of map is given on page 195 of Thompson (equations map.1 and map.2), and the definition ++ is on page 144 (equations ++.1 and ++.2).

9. A ternary tree of A's is either a leaf holding a single value of type A or is a node having a value of type A and three subtrees, (left, middle and right), where each subtree is also a ternary tree of A's. Write a data type definition of a ternary tree of A's.

10. Using your type from the preceding questions, write a definition of function called traverse that takes a ternary tree t and produces a list holding every value that is in tree t, either at a leaf or a node. The order of the list is not important.

11. Say that a data type is traversable if there is a function called traverse that converts it into a list. More spefically, a constructor C is traversable if there is a function traverse :: C a -> [a]. A ternary tree is a special kind of traversable data structure.

    1. Write a class definition for traversable data structures.
    2. Write a definition that makes ternary tres traversable.

12. The list of Fibonacci numbers is defined to be [1,1,2,3,5,8,11,...], where each member after the first two is the sum of the two preceding members. Write a definition of this infinite list. The definition should be designed so that computing a prefix of length n can be done using no more than n additions. (Ignore the fact that the number grow very large quickly.)