=======================================================================================
=== ===
=== 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 → int list × int list
f1 receives two lists of integers, l1 and l2.
It removes the common prefix of l1 and l2, that is, the head elements of l1 and l2 which are identical (in the same order).
It returns two lists: l1 without the common prefix, and l2 without the common prefix.
Examples
f1 [] [] ~~> [], []
f1 [ 1 ; 2 ; 2 ] [ 1 ; 3 ; 3 ] ~~> [ 2 ; 2 ], [ 3 ; 3 ] (* The common prefix is [1] *)
f1 [ 1 ; 2 ; 3 ] [ 1 ; 2 ; 3 ] ~~> [], []
f1 [ 1 ; 2 ; 3 ] [ 1 ; 2 ; 2 ; 2 ] ~~> [ 3 ], [ 2 ; 2 ]
f1 [ 1 ; 2 ; 3 ] [ 0 ; 1 ; 2 ; 3 ] ~~> [ 1 ; 2 ; 3 ], [ 0 ; 1 ; 2 ; 3 ]
----- Question 2 ★ -----
Write a function f2 : exn option → int
f2 receives an exception option, e.g. None, or Some Not_found, or Some End_of_file, etc. (exceptions are standard values of type exn)
If f2 receives an exception, it raises it.
If not, it returns 0.
Examples
f2 None ~~> 0
f2 (Some Not_found) ~~> (the exception Not_found is raised)
f2 (Some End_of_file) ~~> (the exception End_of_file is raised)
----- 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 : int count list → int count list
f3 receives a list l0, containing integer counts (i.e. the values are integers).
It must return the same list, where the vv and nn values have been switched.
Examples
let l1 = [ { vv = 9 ; nn = 10 } ]
let l2 = { vv = 31 ; nn = 5 } :: l1
f3 [] ~~> []
f3 l1 ~~> [ { vv = 10 ; nn = 9 } ]
f3 l2 ~~> [ { vv = 5 ; nn = 31 } ; { vv = 10 ; nn = 9 } ]
----- 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 AT LEAST ONE filter 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 [] l1 ~~> []
f4 [ Equal 'B' ; GT 3 ] l1 ~~> [ { vv = 'B' ; nn = 5 } ; { vv = 'B' ; nn = 10 } ; { vv = 'B' ; nn = 4 } ; { vv = 'A' ; nn = 4 } ]
f4 [ Equal 'A' ; GT 5 ] l1 ~~> [ { vv = 'A' ; nn = 2 } ; { vv = 'B' ; nn = 10 } ; { vv = 'A' ; nn = 4 } ]
----- 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 l, containing 'a counts (the values are of type 'a).
f5 compacts adjacent counts having the same value (and their counts are added),
hence if the list contains two consecutive elements { vv = VV ; nn = 5 } and { vv = VV ; nn = 10 }
then the two elements are replaced by { vv = VV ; nn = 15 }
This compactions occur if and only if both values are the same (here both are equal to VV).
Besides, it must also compact longer sequences with the same value (e.g. three consecutive elements with VV)
Examples
let l1 = [ { vv = 9 ; nn = 10 } ]
let l2 = { vv = 31 ; nn = 5 } :: { vv = 31 ; nn = 1 } :: { vv = 31 ; nn = 10 } :: { vv = 9 ; nn = 2 } :: l1
f5 [] ~~> []
f5 l1 ~~> l1
f5 l2 ~~> [ { vv = 31 ; nn = 16 } ; { vv = 9 ; nn = 12 } ]
----- 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 max value of this value's counts in l.
Hence, if the list l contains two elements { vv = VV ; nn = 5 } and { vv = VV ; nn = 10 }
and no other element with vv = VV, then the resulting list must contain { vv = VV ; nn = 10 } (we keep the max only for VV).
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 = 10 } ; { vv = 9 ; nn = 4 } ]
----- 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 ;;