=======================================================================================
=== ===
=== Sujet de l'examen ===
=== ===
=======================================================================================
- Pour valider chaque fonction, vous devez obligatoirement effectuer le test automatique
qui vous indiquera si votre fonction est correcte.
Le test automatique est déjà présent dans le programme à compléter ('✔✔✔ Check your answer').
- Les fonctions n'ont pas besoin d'être tail-recursive, sauf lorsque c'est demandé explicitement.
- Vous avez le droit d'utiliser les fonctions de la librairie standard (p. ex. List.filter), mais sans y être obligé.
En particulier, vous pouvez utiliser List.rev pour construire une liste inverse si besoin.
- Vous pouvez créer et utiliser autant de fonctions auxiliaires que vous souhaitez.
- Les énoncés sont en anglais afin de rester familier avec le vocabulaire des leçons et exercices.
- Le barème pour chaque question est indiqué de manière approximative avec des étoiles ★★.
=======================================================================================
----- Question 1 ★ -----
Write a function f1 : int list → int list
f1 receives a list of integers, l1.
It removes the prefix of l1 that is sorted (the prefix must be in ascending order).
It returns the rest of the list, starting at the first element which is not sorted.
Examples
f1 [] ~~> []
f1 [ 1 ; 2 ; 2 ; 3 ] ~~> [] (* They are all sorted *)
f1 [ 9 ] ~~> [] (* [9] is a sorted singleton *)
f1 [ 1 ; 1 ; 2 ; 0 ] ~~> [ 0 ] (* 1 ; 1 ; 2 is a sorted prefix. 1 ; 1 ; 2 ; 0 is not sorted, so we return the tail of the list starting at 0. *)
f1 [ 1 ; 2 ; 0 ; 4 ; 5 ; 6 ] ~~> [ 0 ; 4 ; 5 ; 6 ] (* The sorted prefix is 1 ; 2 *)
f1 [ 2 ; 1 ; 3 ; 4 ] ~~> [ 1 ; 3 ; 4 ] (* The sorted prefix is only 2 *)
----- Question 2 ★ -----
Write a function f2 : (unit → unit) → exn option
f2 receives a function g with type unit -> unit.
f2 tries to apply g. If g returns a value (which is necessarily unit), f2 returns None.
If g raises an exception e, f2 returns Some e
Examples
f2 (λ().()) ~~> None
f2 (λ().raise Not_found) ~~> Some Not_found
f2 (λ().raise End_of_file) ~~> Some End_of_file
----- Question 3 ★ -----
Open types_count.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f3 : ∀ α . α count list → α list × int list
f3 receives a list l0, containing 'a counts (the values are of type 'a).
It must return two lists l1 and l2, which both have the same size as l0.
l1 is the list of (vv) values.
l2 is the list of (nn) counts.
Examples
let l1 = [ { vv = true ; nn = 10 } ]
let l2 = { vv = false ; nn = 5 } :: l1
f3 [] ~~> [], []
f3 l1 ~~> [ true ], [ 10 ]
f3 l2 ~~> [ false ; true ], [ 5 ; 10 ]
----- Question 4 ★★ -----
Open types_count.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f4 : ∀ α . α filter list → α count list → α count list
f4 receives a list of filters ff (of type 'a filter) and a list of counts ll.
It returns a list of elements of ll that satisfy ALL the filters in ff, in the same order as in ll.
Examples
let l1 = [ { vv = 'B' ; nn = 5 } ; { vv = 'A' ; nn = 2 } ; { vv = 'B' ; nn = 10 } ; { vv = 'B' ; nn = 4 } ; { vv = 'A' ; nn = 4 } ]
f4 [ Equal 'B' ; GT 4 ] l1 ~~> [ { vv = 'B' ; nn = 5 } ; { vv = 'B' ; nn = 10 } ]
f4 [] l1 ~~> l1
f4 [ Equal 'A' ; GT 4] l1 ~~> []
----- Question 5 ★ -----
Open types_count.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f5 : ∀ α . α count list → α count list
f5 receives a list l1, containing 'a counts (the values are of type 'a).
f5 returns a list l2 having one element less than l1.
The first element of l2 contains the 'vv' of the second element of l1, and the 'nn' of the first element of l1.
More generally, the nth element of l2 contains the 'vv' of the n+1th element of l1, and the 'nn' of the nth element of l1.
Examples
let l1 = [ { vv = 'E' ; nn = 10 } ]
let l2 = { vv = 'A' ; nn = 2 } :: { vv = 'B' ; nn = 4 } :: { vv = 'C' ; nn = 6 } :: { vv = 'D' ; nn = 8 } :: l1
f5 [] ~~> []
f5 l1 ~~> []
f5 l2 ~~> [ { vv = 'B' ; nn = 2 } ; { vv = 'C' ; nn = 4 } ; { vv = 'D' ; nn = 6 } ; { vv = 'E' ; nn = 8 } ]
----- Question 6 ★★ -----
Open types_count.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f6 : ∀ α . α count list → α count list
f6 receives a list l, containing 'a counts (the values are of type 'a).
It returns a list of counts, where each (vv) value appears only once,
and its associated count is the mean value of this value's counts in l.
The mean value is still an integer, do not use float computations.
Hence, if the list l contains both elements { vv = VV ; nn = 5 } and { vv = VV ; nn = 10 }
and no other element having vv = VV, then the resulting list must contain { vv = VV ; nn = 7 } since 7 = (10+5)/2.
The order of the elements in the result list does not matter.
Examples
let l1 = [ { vv = 9 ; nn = 4 } ]
let l2 = { vv = 31 ; nn = 5 } :: { vv = 9 ; nn = 2 } :: { vv = 31 ; nn = 10 } :: { vv = 31 ; nn = 4 } :: l1
f6 [] ~~> []
f6 l1 ~~> l1
f6 l2 ~~> [ { vv = 31 ; nn = 6 } ; { vv = 9 ; nn = 3 } ]
----- Question 7 ★★ -----
Write a function f7 : ∀ α . α tree → α count list
f7 expects a tree.
Z nodes are empty leaves.
Each count node (C) has a count.
Each sort node (S) has a left subtree, a right subtree, and a comparison value 'cv'.
f7 checks that for each sort node S, all the counts found in the left subtree have 'nn' values that are smaller or equal to cv,
and all the counts found in the right subtree have 'nn' values that are greater or equal to cv.
f7 must return the list, in any order, of all counts that are misplaced (incorrectly located with respect to comparison values).
To put it another way, f7 returns the list of all counts c such that there exists a sort node S(_, cv, _) such that c is inside the left subtree and c.nn > cv, or c is inside the right subtree and c.nn < cv.
Caution :
- If a given count node in the tree is misplaced because it breaks several conditions, it must be added only once to the misplaced list, not several times.
- But the misplaced list may contain duplicates if two count nodes with equal count values are at two different locations in the tree and both are misplaced.
Examples
Too see examples, use q7_info 401 ;; in ocaml-top
q7_info 401 ;;
q7_info 14808 ;;
q7_info 15420 ;;