CSE 341, Winter 1997

D. Notkin

Quiz #1
1/30/97

 

This quiz covers functional programming and ML. It is open book, open note, closed neighbor. Remember, there will be three quizzes, collectively worth 25% of your total grade; the best two quizzes will each be worth 10% of the total, and the weakest of the three will be worth 5% of the total. There are 100 points on the quiz; not all points are equally difficult, so be sure to use your time wisely. The quizzes will all be collected when the bell rings; no quizzes can come in late.

 

 

Question

Possible Points

Actual Points

1

20

 

2

20

 

3

30

 

4

10

 

5

10

 

6

10

 

Total

100

 

 

 

 

  1. (20 total points) What do each of the following ML expressions evaluate to (you need only give the value, not the type of the value)? If the expression is erroneous, state why.
    1. tl [[2,3],[4,5,6]];

      [[4,5,6]]




    2. (hd (tl (explode "snork")))^(hd (explode "snork"));

      "ns"



    3. val q = (1,2,3,[4,5,6]);
      #3(q)+hd(#4(q));
      (* just give the value of this expression *)

      7




    4. length (map (fn(x)=>x*x+1-x*4+9) [6,5,4,1,2,3]);

      6





    5. map (fn(x)=>3*x+1); (* give the type of the expression, if
      it is well-defined *)

      int list -> int list
  2. (20 total points) Write ML code (but not function definitions) that:
    1. Takes any list l as input and returns a list of equal length where every element in the returned list has the value "snork".

      map (fn _ => "snork") l





    2. Takes a string s as input and returns the length of the string (without using the size function).

      length (explode s)




    3. Takes any tuple t with two elements any returns a tuple with the elements in the reverse order.

      (#2(t),#1(t))





    4. Take a list of strings ls and returns a list containing the strings that are at most three characters long.

      filter ((fn(x)=>(size(x) <= 3)), ls)






    5. Defines a type abbreviation (type) for a list of triples, the first two components of which have the same type and the third component of which is of some (possibly) different type.

    type ( '‘ a ', ’b) snork = ' (‘a' * ‘'a * ‘b) list

     

  3. (30 total points) Circle true or false to each of the following questions.
    1. True or false: In ML it is easy to call an anonymous function recursively.
    2. True or false: Every ML function takes exactly one argument.
    3. True or false: ML’s andalso and orelse operators are examples of eager evaluation.
    4. True or false: A let construct in ML allows you to change the state of a variable in an environment.
    5. True or false: Pattern matching in ML allows you to define functions that you could not define without pattern matching.
    6. True or false: It is impossible to define mutually recursive datatypes in ML.
    7. True or false: Using ref variables in ML generally destroys the property of referential transparency.
    8. True or false: In theory, it doesn’t matter if you pick ML or C++ to write any given program.
    9. True or false: In practice, it doesn’t matter if you pick ML or C++ to write any given program.
    10. True or false: One advantage of type inferencing is that it will usually determine the most general types of functions and values.
    11. True or false: A polymorphic function is one that uses different implementations when applied to different types of operands.
    12. True or false: If you use pattern matching to define an ML function, you must list patterns that exhaustively define all possible cases.
    13. True or false: Referential transparency allows you to reason about the global meaning of a program by composing the meanings of the individual pieces.
    14. True or false: ML types and datatypes can both have multiple constructors.
    15. True or false: ML can infer types that have type variables, but ML programmers cannot write ML constructs in terms of type variables.

  4. (10 points) Rewrite the following functions using pattern matching.

    fun fork x =
    if x = nil then 0
    else 1 + fork (tl x);

    fun snork x =
    if x = nil then 0
    else fork (hd x) + snork (tl x);

    fun fork nil = 0
    | fork (_::xs) = 1 + (fork xs);

    fun snork nil = 0
    | snork (x::xs) = (fork x) + (snork xs);

  5. (10 total points) Consider the following function:

    fun bork G nil x = x
    | bork G (y::ys) x = G(y, (bork G ys x));
    1. (4 points) What is the type of bork?


      (‘a * ‘b -> ‘b) -> ‘a list -> ‘b -> ‘b










    2. (3 points) What is the type of bork (fn(a:string,x)=>a^x);


      string list -> string -> string












    3. (3 points) What does the following expression evaluate to?

      (
      bork (fn(a:string,x)=>a^x) ["ab","cdef"] "xyz";

      "abcedfxyz"

  6. (10 total points)
    1. Write a function that takes a non-negative integer as a parameter and returns a list consisting of the integers from 1 to the parameter’s value. For example:

      -
      upto 7;
      val it = [1,2,3,4,5,6,7];


      fun upto 0 = nil
      | upto N = (upto (N-1))@[N];

















    2. Write a function take that takes a list and a non-negative integer i as a parameter and returns a list consisting of the first i elements in the list. If the integer is longer than the length of the list, return the entire list. For example:

      -take [4,1,2,4,8] 3;
      val it = [4,1,2]

      fun take nil i = nil
      | take L 0 = nil
      | take (x::xs) i = x::(take xs (i-1));