=======================================================================================
=== ===
=== 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 → bool
f1 receives two lists l1 and l2.
It returns true iff the list l1 is a suffix of l2.
That is, l2 is of the form x1 :: x2 :: ... :: xn :: l1. This includes the case where l2 equals l1.
Remember: to compare lists, you may use = (do not use ==).
Examples
f1 [1;2] [3;1;2] ~~> true
f1 [1;2] [1;2] ~~> true
f1 [1;2] [3;1] ~~> false
f1 [1;2] [2;1] ~~> false
f1 [1] [3;1] ~~> true
----- Question 2 ★ -----
Write a function f2 : (unit → unit) → exn option
f2 receives a function g of type unit → unit.
It applies g. If g raises an exception e, f2 returns Some e.
If g does not raise any exception, f2 returns None.
Examples
f2 (λ().()) ~~> None
f2 (λ().(raise Not_found)) ~~> Some Not_found
----- 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 : catalog → catalog
f3 receives a catalog of tshirts.
It must return the same catalog, with elements in the same order, but without tshirts of size XL.
Examples
f3 [] ~~> []
f3 [ { l-tshirt } ; { xl-tshirt } ; { m-tshirt } ] ~~> [ { l-tshirt } ; { m-tshirt } ] (this is not ocaml syntax)
Too see other examples, use q3_info 4100 ;; in ocaml-top
q3_info 4100 ;;
q3_info 5201 ;;
----- 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 : color → int → catalog → int
f4 receives three arguments: a color c, a price p, and a catalog of tshirts.
It must return the number of t-shirts in the catalog which have the given color c AND whose price is less or equal than p.
Examples
f4 White 10 [] ~~> 0
f4 White 25 [ { white-tshirt-price-10 } ; { blue-tshirt-price-20 } ; { white-tshirt-price-30 } ] ~~> 1 (this is not ocaml syntax)
f4 Blue 15 [ { white-tshirt-price-10 } ; { blue-tshirt-price-20 } ; { white-tshirt-price-30 } ] ~~> 0
Too see other examples, use q4_info 4100 ;; in ocaml-top
q4_info 4100 ;;
q4_info 5201 ;;
----- 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 : size → catalog → color list
f5 receives two arguments: a size z and a catalog of tshirts.
It must return the list of colors available for tshirts of the given size z.
Colors must occur only once in the list. The order of the list does not matter.
Examples
f5 L [] ~~> []
f5 L [ { white-l-tshirt } ; { blue-l-tshirt } ; { white-l-tshirt } ] ~~> [ White ; Blue ] (this is not ocaml syntax)
f5 XL [ { white-l-tshirt } ; { blue-xl-tshirt } ; { white-l-tshirt } ] ~~> [ Blue ]
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 → (color × tshirt list) list
f6 receives a catalog of tshirts.
It must return a list associating each color to a list of tshirts of this color.
That is, an association list containing elements of the form (color, list-of-tshirts)
The order of the association list and the order of inner lists does not matter.
Examples
f6 [] ~~> []
f6 [ { white-tshirt1 } ; { blue-tshirt2 } ; { white-tshirt3 } ] ~~> [ (White, [ w-tshirt1 ; w-tshirt3 ]) ; (Blue, [ b-tshirt2 ]) ] (this is not ocaml syntax)
Too see other examples, use q6_info 4100 ;; in ocaml-top
q6_info 4100 ;;
q6_info 5201 ;;
----- 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 list
f7 receives a tree of tshirts.
It must return the list of ids of all the nodes that contain an XL tshirt.
The order of the list does not matter. Since several nodes may have the same id, an id may occur several times in the resulting list.
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 ;;