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