=======================================================================================
=== ===
=== 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 : ∀ α . α → α list → α list → α list
f1 receives three arguments: an element x, and two lists l1 and l2.
It appends to the left of l1 all elements of l2, except those equal to x, in reversed order.
Elements equal to x in l1 are kept.
Examples
f1 0 [ 1 ; 2 ] [ 3 ; 4 ] ~~> [ 4 ; 3 ; 1 ; 2 ]
f1 0 [ 1 ; 2 ] [ 3 ; 0 ; 4 ] ~~> [ 4 ; 3 ; 1 ; 2 ]
f1 0 [] [ 3 ; 4 ] ~~> [ 4 ; 3 ]
f1 0 [0] [ 3 ; 4 ] ~~> [ 4 ; 3 ; 0 ]
f1 0 [ 1 ; 0 ; 2 ] [] ~~> [ 1 ; 0 ; 2 ]
----- Question 2 ★ -----
Write a function f2 : (unit → unit) → exn → bool
f2 receives a function g and an exception e.
It applies g. If g raises the exception e, f2 returns true.
If g does not raise any exception, or if g raises another exception, f2 returns false.
Examples
f2 (λ().()) Not_found ~~> false
f2 (λ().(raise Not_found)) Not_found ~~> true
f2 (λ().(raise End_of_file)) End_of_file ~~> true
f2 (λ().(raise End_of_file)) Not_found ~~> false
f2 (λ().(raise Not_found)) End_of_file ~~> false
----- Question 3 ★ -----
Open types_tshirt.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f3 : size → color → catalog → int
f3 receives three arguments: a size z, a color c, and a catalog of tshirts.
It must return the number of t-shirts in the catalog which have the given size z AND color c.
Examples
f3 L White [] ~~> 0
f3 L White [ { l-white-tshirt } ; { l-blue-tshirt } ; { l-white-tshirt } ] ~~> 2 (this is not ocaml syntax)
f3 XL Blue [ { l-white-tshirt } ; { l-blue-tshirt } ; { l-white-tshirt } ] ~~> 0
Too see other examples, use q3_info 4100 ;; in ocaml-top
q3_info 4100 ;;
q3_info 5210 ;;
----- Question 4 ★ -----
Open types_tshirt.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f4 : catalog → catalog
f4 receives a catalog of tshirts.
It must return the same catalog, with elements in the same order, but without tshirts whose color is White.
Examples
f4 [] ~~> []
f4 [ { blue-tshirt } ; { white-tshirt } ; { black-tshirt } ] ~~> [ { blue-tshirt } ; { black-tshirt } ] (this is not ocaml syntax)
Too see other examples, use q4_info 2200 ;; in ocaml-top
q4_info 2200 ;;
q4_info 2213 ;;
----- Question 5 ★★ -----
Open types_tshirt.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f5 : color → catalog → string list
f5 receives two arguments: a color c and a catalog of tshirts.
It must return the list of all messages present on tshirts of the given color c.
Messages must occur only once in the list. The order of the list does not matter.
Examples
f5 White [] ~~> []
f5 White [ { white-tshirt-msg1 } ; { white-tshirt-msg2 } ; { white-tshirt-msg1 } ] ~~> [ msg1 ; msg2 ] (this is not ocaml syntax)
f5 Blue [ { white-tshirt-msg1 } ; { blue-tshirt-msg2 } ; { white-tshirt-msg1 } ] ~~> [ msg2 ]
Too see other examples, use q5_info 4100 ;; in ocaml-top
q5_info 4100 ;;
q5_info 5201 ;;
----- Question 6 ★★ -----
Open types_tshirt.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f6 : catalog → (size × tshirt list) list
f6 receives a catalog of tshirts.
It must return a list associating each size to a list of tshirts of this size.
That is, an association list containing elements of the form (size, list-of-tshirts)
The order of the association list and the order of inner lists does not matter.
Examples
f6 [] ~~> []
f6 [ { l-tshirt1 } ; { xl-tshirt2 } ; { xl-tshirt3 } ] ~~> [ (L, [ l-tshirt1 ]) ; (XL, [ xl-tshirt2 ; xl-tshirt3 ]) ] (this is not ocaml syntax)
Too see other examples, use q6_info 4100 ;; in ocaml-top
q6_info 4100 ;;
q6_info 5010 ;;
----- Question 7 ★★ -----
Open types_tshirt.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f7 : tshirt tree → int
f7 receives a tree of tshirts.
It must return the id of the node with the least expansive tshirt.
If several nodes contain tshirts with the minimum price, choose the topmost-leftmost one (i.e. the first one found in a depth-first left-to-right traversal).
Examples
Too see examples, use q7_info 4100 ;; in ocaml-top
q7_info 4100 ;;
q7_info 5201 ;;
----- Question 8 ★★+½★ -----
Open types_tshirt.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f8 : size list → color list → catalog → int tree
f8 receives three arguments: a non-empty list of sizes [ s1 ; s2 ; ... sn ], a non-empty list of colors [ c1 ; c2 ; ... ; ck ], and a catalog.
As an example, the list of sizes can be [ S ; M ; S ]
The list of colors can be [ White ; White ; Blue ; Black ; Blue ]
It must return a tree, of type int tree. The tree values indicate how many tshirts of the catalog have size s1, s2, ... and colors c1, ... ck.
More precisely, the tree is built as follows:
- All nodes (including leaves) have an id equal to 0.
*** Structure of the tree: 2 levels.
- The top node has n children (n is the length of the size list). These are level-1 children: child s1, child s2, ... child sn.
- Each of these children has itself k children (k is the length of the color list). These are level-2 children: subchild c1, ... subchild ck.
- Level-2 children are leaves.
- It should be obvious that the number of leaves is k*n.
*** Values on nodes
- The value to be found on a node depends on its position in the tree:
- Root: its value is the number of tshirts (in the catalog).
- Level-1 child (child si): the value is the number of tshirts of size si.
- Level-2 child (subchild si.cj): the value is the number of tshirts of size si AND color cj.
Examples
Too see examples, use q8_info 21750 ;; in ocaml-top
q8_info 21750 ;;
q8_info 21752 ;;