CSCI 3675 practice questions for quiz 3

Computer Science 3675
Fall 2016
Practice Questions for Quiz 3

Suppose that function f is defined by
f(x, y) = (y, head(x))
What is the most general polymorphic type of f? Use Greek letters for type variables.

Answer
Suppose that function f is defined by
f(x, y, z) = x :: y :: z
What is the most general polymorphic type of f? Use Greek letters for type variables.

Answer
Suppose that function f is defined by
f x y = y x
What is the most general polymorphic type of f? Use Greek letters for type variables. Notice that f is curried.

Answer
Given definition
```
   f x y = (x+1)::y.
```
1. What kind of thing is x (a number, a list or a function)? Answer
2. What kind of thing is y (a number, a list or a function)? Answer
3. What kind of thing is f x y (a number, a list or a function)? Answer
4. What kind of thing is f x (a number, a list or a function)? Answer
You are given the following function definition.
```
    f x y z = y x (x::z)
```
1. What kind of thing is parameter z? (A number, a list, a function, or something else)? Answer
2. What kind of thing is parameter y? (A number, a list, a function, or something else)? Answer
3. What kind of thing does expression f (2) yield? (A number, a list, a function, or something else? Is this expression allowed?) Answer
Given the Cinnameg type definition
```
  Type Frog =
      green  String
    | yellow (Integer, Integer)
  %Type
```
Which of the following are sensible? Answer all that are sensible. (Sensible means that they compile and do not lead to failure when they run.) Treat each as a separate problem.
1. ! kermit = frog("Kermit", 3, 4).
2. ! kermit = green("Kermit").
3. ! kermit = yellow("Kermit").
4. ! kermit = yellow(3,4).
5. Match yellow(x,y) =~ yellow(4,7).
6. Match green(s) =~ yellow(4,7).
Answer
Using the type Frog from the preceding question, define a function size(f ) so that: if f is a Frog of the form green(name), then size(f ) is the length of name; and if f is a Frog of the form yellow(m, n) then size(f ) is m.

Answer
Imagine that lists are not available. Write a type definition in Cinnameg of type StringList where a value of type StringList is a linked list of strings. Then do whatever is necessary to ensure that functions head, tail, nil? and operator :: are defined. Assume that :: has already been specified to be a binary operator. nil?(x) is true just when x is an empty list. Do not worry about what happens when the head or tail of an empty list is computed.
Hint. There are two kinds of lists: empty lists and nonempty lists. What information does a nonempty list need to hold? Think of linked lists.

Answer
Suppose that type Tree is defined as follows in Cinnameg.
```
Type Tree =
    leaf    Integer
  | nonleaf (Tree, Tree)
%Type
```
So a tree consists of leaves and nonleaves. Each leaf holds an integer. When we think of a tree, we think of the entire collection of leaves and nonleaves, including those in the subtrees.

Write a definition of sum(t), which yields the sum of all of the numbers in leaves of tree t.

Answer
Using the type Tree from the preceding question, write a definition of toList(t), which yields a list of all numbers in leaves in tree t.

Answer
Repeat the previous exercise, but do not use concatenation.

Answer
Consider the following definition written in Cinnameg.
```
    Define f(n) = (:n*n :: f(n+1):).
```
What value does expression f(2) compute? Give the full value, as it would be if it were examined. (It suffices to give a clear description of the full value.) Evaluating a promise does not change the value that is represented, it only changes the representation of the value.

Answer
Consider the following definition written in Cinnameg.
```
    Define f(n) = (: n :: f(n*n) :).
```
What value does expression f(2) compute? Give the full value, as it would be if it were examined.

Answer
Write an equational definition of rfold(i, f, L) so that rfold(i, f, [a,b,c]) = f (a, f (b, f (c, i))). Generalize to an arbitrarily long list.
To get a better understanding of this, suppose that the function (f ) is a binary operator * (whose meaning could be anything), where operator * is right-associative. That is, a*b*c means a*(b*c). Then rfold(i, *, [a,b,c]) = a*b*c*i and rfold(x, *, [a,b,c,d]) = a*b*c*d*x.

By definition, rfold(i, f, [ ]) = i.

Answer
What is the value of each of the following Cinnameg expressions? (foldLtoR i f x) is a left-to-right fold with initial value i and function f on list x.
1. map (x |-> x + 5) [2,4,6]. Answer
2. map tail [[2,5], [4], [6,5,4]]. Answer
3. foldLtoR 1 (+) [2,3,4,5]. Answer
Function select is written so that (select p x) returns the first member m of list x such that p(m) is true. (For the purposes of this question, it will not matter what select does when there is no such m.) Notice that p is a predicate, a function that produces a boolean result. Predicate odd? returns true on an odd integer and false on an even integer. (The question mark is part of the name of function odd?.) For example, (select odd? [2,3,4,5,6]) = 3.
1. What is the type of function odd? Answer
2. What is the most general polymorphic type of function select? Keep in mind that select is curried. Answer
3. What is the value of Cinnameg expression
  map (select odd?) [[2,3,4,5], [1,2,3,4], [2,4,6,7,8]]? Answer
By choosing among the operations foldLtoR, foldRtoL and map write a Cinnameg definition for each of the following that does not make direct use of recursion or loops.
1. Write a definition of a function called doubleAll that takes a list x of numbers as its parameter and produces a list of the doubles numbers in list x as its result. For example, doubleAll([5,2,19,3]) = [10,4,38,6].
  
  Answer
2. Write a definition of a function called product so that product(x) yields the product of all of the members of list x, where x is a list of numbers. (Product means multiply.)
  
  Answer

Computer Science 3675 Fall 2016 Practice Questions for Quiz 3

Computer Science 3675
Fall 2016
Practice Questions for Quiz 3