======================================================================================= === === === 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 ;;