=======================================================================================
=== ===
=== 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 ★ -----
Open types_middle.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f1 : string list → person list
f1 receives a list of names (strings).
It returns a list of persons, consisting in Hobbits with the given name, and a size of 110 cm.
Examples
f1 [] ~~> []
f1 [ "Merry" ] ~~> [ Hobbit("Merry", 110) ]
f1 [ "Merry" ; "Sam"] ~~> [ Hobbit("Merry", 110) ; Hobbit("Sam", 110) ]
----- Question 2 ★ -----
Open types_middle.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f2 : person list → region list
f2 receives a list of persons.
It returns the list of regions of elves, in the same order.
Examples
f2 [] ~~> []
f2 people1 ~~> [ Mirkwood ; Mirkwood ; Imladris ; Imladris ; Imladris ; Lorien ; Mirkwood ; Imladris ; ... ]
Too see examples, use q2_info 135 ;; in ocaml-top
q2_info 135 ;;
q2_info 16520 ;;
----- Question 3 ★ -----
Open types_middle.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f3 : person list → int
f3 receives a list of persons.
It returns the size (in cm) of the tallest hobbit. If the list contains no hobbit, it returns 0.
Examples
f3 [] ~~> 0
f3 people1 ~~> 121
----- Question 4 ★ -----
Open types_middle.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f4 : (person → bool) → person list → bool
f4 receives two arguments: a predicate and a list of persons.
It returns true if and only if the predicate is true on all dwarves of the list.
Examples
is_young is predefined. It indicates if a dwarf is younger than 120 years old.
is_under_200 is predefined. It indicates if a dwarf is younger than 200 years old.
f4 is_young [] ~~> true
f4 is_young [ Dwarf ("Fili", 115) ; Dwarf ("Kili", 112) ] ~~> true
f4 is_young people1 ~~> false
f4 is_under_200 people1 ~~> true
----- Question 5 ★★ -----
Open types_middle.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f5 : person list → (region × (person list)) list
f5 receives a list of persons.
It returns an association list of three pairs. Each pair is of the form (region, list-of-elves).
It lists, for each region, the elves coming from that region.
The order of the regions and the order of the elves in each region does not matter.
Examples
f5 [] ~~> [ (Lorien, []) ; (Imladris, []) ; (Mirkwood, []) ]
f5 people1 ~~> [ (Lorien, [ Elf ("Galathil", Lorien) ; Elf ("Galadriel", Lorien) ; Elf ("Celeborn", Lorien) ; Elf ("Orophin", Lorien); Elf ("Haldir", Lorien)]) ;
(Imladris, [ Elf ("Arwen", Imladris) ; Elf ("Celebrian", Imladris) ; Elf ("Lindir", Imladris) ; Elf ("Elladan", Imladris) ; Elf ("Gildor", Imladris) ; Elf ("Elrond", Imladris)]) ;
(Mirkwood, [ Elf ("Amdir", Mirkwood) ; Elf ("Legolas", Mirkwood) ; Elf ("Tauriel", Mirkwood) ; Elf ("Oropher", Mirkwood) ; Elf ("Thranduil", Mirkwood)]) ]
----- Question 6 ★★ -----
Open types_middle.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f6 : person list → (int × (string list)) list
f6 receives a list of persons.
It returns an association list. Each pair in the list is of the form (size, list-of-names).
It lists, for each size found in the list of persons, the names of the hobbits with exactly that size.
The order of the sizes and the order of the hobbit names in the list does not matter.
Each size must occur only once in the association list.
(Although this question looks very much like question 5, it is actually more difficult, because the different sizes are not known in advance.)
Examples
f6 [] ~~> [ ]
f6 people1 ~~> [ (82, ["Doderic"]) ;
(98, ["Gorbulas" ; "Drogo"]) ;
(102, ["Bilbo"]) ;
(104, ["Bill" ; "Adamanta"]) ;
(106, ["Sam" ; "Rosa" ; "Filibert"]) ;
(109, ["Frodo"]) ;
(121, ["Merry" ; "Pippin"]) ]
----- Question 7 ★★★ -----
Open types_middle.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f7 : ∀ α . string → α room → α list
f7 receives a name (string) and a start room.
It must find if a person with the given name exists in a room reachable from the start room.
This is done by recursively exploring all the possible paths. (The exploration should consider out1 before out2.)
If nobody with the given name can be found, it returns the empty list.
If a person can be found with the expected name, f7 returns the path from the starting room to the person. A path is a list of tags.
For instance, if the starting room is R1 (with tag t1) and the person we are looking for is in R1, the function returns [ t1 ]
If the person is in room R2 (tag t2), which is immediately after room R1, the function returns [ t1 ; t2 ]
Examples
Too see examples, use q7_info 4100 ;; in ocaml-top
q7_info 4100 ;;
q7_info 15403 ;;
q7_info 20218 ;;