Exercises

From the midterm project

• Question 10: regarding nested let-expressions

Mandatory exercises

• Exercise 1: computing the size of the list of successive suffixes of a list.
• Exercise 4: implementing the list analogue of String.mapi
• Exercise 8: exhibiting two sets that will make traced_set_intersection emit a given pattern of calls and returns
• Exercise 11: using set-theoretic identities to beef up the unit tests
• Exercise 16: implementing union, intersection, and difference for sets of integers represented as sorted lists without repetition

Recommended exercise

• Exercise 12: implementing the symmetric difference of sets

Exercise 17

Consider the two following functions:

let foo f g xs =
 (* foo : ('a -> 'b) -> ('c -> 'a) -> 'c list -> 'b list *)
  List.map f (List.map g xs);;

let bar f g xs =
 (* bar : ('a -> 'b) -> ('c -> 'a) -> 'c list -> 'b list *)
  List.map (fun x -> f (g x)) xs;;

1. Are the functions denoted by foo and bar equivalent, when they are applied to pure (i.e., effect free) functions?
2. Are the functions denoted by foo and bar equivalent, when they are applied to impure (e.g., tracing) functions?

Solution for Exercise 17

First of all, let us analyze foo and bar:

• given two functions f and g and a list xs, the function denoted by foo first maps g over xs, yielding a new list, and then maps f over this new list, yielding a resulting list
• given two functions f and g and a list xs, the function denoted by bar maps the composition of f and g over xs, yielding a resulting list.

Thus equipped, here are the answers to the questions:

1. Let us pick two pure functions: one that increments its argument by 10, and one that increments its argument by 1:

   • by the analysis above, given these two functions and a list, the function denoted by foo

     1. traverses this list, applies the second function (the one that increments its argument by 1) to each element of this list, and constructs the list of the incremented results, which is a new list with the same length as the given list; and
     2. traverses this new list of incremented results, applies the second function (the one that increments its argument by 10) to each element of this new list, and constructs the list of the incremented results, which is the resulting list and has the same length as the new list;

     so all in all, given a list, the function denoted by foo returns a final list with the same length as the given list, but where all the elements are incremented by 1 + 10 = 11:

     # foo (fun j -> j + 10) (fun i -> i + 1) [0; 1; 2; 3; 4; 5];;
     - : int list = [11; 12; 13; 14; 15; 16]
     #
     

   • by the analysis above, given two functions and a list, the function denoted by bar

     1. manufactures a new function that composes the two functions; given an integer, this composite function first increments it by 1, and then increments the result by 10; in other words, this function increments its argument by 11;
     2. traverses the given list, applying the composite function to each element of this list, and constructs the list of the results; this list is the resulting list and has the same length as the given list;

     so all in all, given a list, the function denoted by bar returns a list with the same length as the given list, but where all the elements are incremented by 11:

     # bar (fun j -> j + 10) (fun i -> i + 1) [0; 1; 2; 3; 4; 5];;
     - : int list = [11; 12; 13; 14; 15; 16]
     #
     

   This leads us to conclude that the functions denoted by foo and bar are equivalent when applied to pure functions, because the order in which these pure functions are applied does not matter.

2. As a corollary, even though they return the same result, the functions denoted by foo and bar are not equivalent when applied to impure functions, because the order in which these impure functions are applied does matter. Their effects are observationally distinct:

   # foo (fun j -> let () = Printf.printf "ten %s ->\n" (show_int j) in j + 10)
         (fun i -> let () = Printf.printf "one %s ->\n" (show_int i) in i + 1)
         [0; 1; 2; 3; 4; 5];;
   one 0 ->
   one 1 ->
   one 2 ->
   one 3 ->
   one 4 ->
   one 5 ->
   ten 1 ->
   ten 2 ->
   ten 3 ->
   ten 4 ->
   ten 5 ->
   ten 6 ->
   - : int list = [11; 12; 13; 14; 15; 16]
   # bar (fun j -> let () = Printf.printf "ten %s ->\n" (show_int j) in j + 10)
         (fun i -> let () = Printf.printf "one %s ->\n" (show_int i) in i + 1)
         [0; 1; 2; 3; 4; 5];;
   one 0 ->
   ten 1 ->
   one 1 ->
   ten 2 ->
   one 2 ->
   ten 3 ->
   one 3 ->
   ten 4 ->
   one 4 ->
   ten 5 ->
   one 5 ->
   ten 6 ->
   - : int list = [11; 12; 13; 14; 15; 16]
   #
   

   Analysis:

   • the function denoted by foo first applies the function that increments its argument by 1 (witness the successive traces of one), and then applies the function that increments its argument by 10 (witness the successive traces of ten), whereas
   • the function denoted by bar interleaves the function that increments its argument by 1 and the function that increments its argument by 10 (witness the interleaved traces of one and ten).

Version

Moved Exercise 1 where it belongs, i.e., from the exercises of Week 07 to the exercises of Week 08 [16 Mar 2020]

Added Question 10b from the midterm [15 Mar 2020]

Created [14 Mar 2020]