For today's OCaml part we briefly covered modules as described in Hickey, chap.11+12 (and parts of chap.13). You shouldn't spend time on the gory details of, e.g., "sharing constraints" in chap.13, though. For this afternoon's exercises I ask you to consider the following: 1. Consider the uploaded module implementing Patricia trees. You can either copy the source code to your working directory or install it using these 5 steps (please ignore the friendly instructions printed by ./configure): ./configure make ptset.cmi make ptmap.cmi make make install then the package should show up within OCaml's toploop if you afterwards query it: #use "topfind";; (* Windows users should instead build a custom #top-level *) #list;; Alternatively run 'opam install ptset' to install a slightly newer version. If you install with 'make' or 'opam' you can afterwards compile a file day4.ml that uses ptset with the command: ocamlbuild -use-ocamlfind -package qcheck,ptset day4.byte Test the implementation of integer sets (blackbox over the interface) against a model of int sets based on lists. You need - to select a set of operations (start small) - to implement a little language and an accompanying generator of integer set operations - to implement an interpreter of these set operations - to implement the individual operations in the model - to implement abstraction of the Patricia trees - and finally to test that for an arbitrary set our observations and the set "state" agrees 2. a. Write a shrinker for your language of integer set operations from 1. b. Introduce an error in your model c. Compare the output (for a fixed seed) with and without shrinking 3. Consider the model for Ptset.mem a. Change it to add 'n+1' instead of its parameter 'n' b. Does QuickCheck find the error? Why/why not? c. Write a classifier that partitions pairs of instruction sequences and integers i based on whether i is mentioned in the instruction sequence d. Change the pair generator to generate more cases in both categories of the classifier 4. (for the daring) Write an algebraic specification for sets. QuickCheck either Patricia trees, Red-black trees, or the Set module from OCaml's standard library