=======================================================================================
=== ===
=== 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 : person list → string list
f1 receives a list of persons.
It returns the list of names (strings) of dwarves, in the same order.
Examples
f1 [] ~~> []
f1 people1 ~~> [ "Thorin"; "Oin"; "Bofur"; "Nori"; "Bombur"; "Fili"; "Gloin"; "Bifur"; "Kili"; "Balin"; "Dwalin"; "Ori"; "Dori" ]
----- 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 : string → region list → person list
f2 receives a name (string) and a list of regions.
It returns a list of persons, consisting in Elves having all the given name, and with the regions given in the list (in the same order).
Examples
f2 "Legolas" [] ~~> []
f2 "Legolas" [ Lorien ] ~~> [ Elf("Legolas", Lorien) ]
f2 "Legolas" [ Imladris ; Mirkwood ] ~~> [ Elf("Legolas", Imladris) ; Elf("Legolas", Mirkwood) ]
----- 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 age of the youngest dwarf. If the list contains no dwarf, it returns max_int. (max_int is already defined)
Examples
f3 [] ~~> max_int
f3 people1 ~~> 92
----- 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 for at least one elf in the list.
Examples
is_legolas is predefined. It indicates if an Elf name is Legolas.
from_lorien is predefined. It indicates if an Elf comes from Lorien.
f4 is_legolas [] ~~> false
f4 is_legolas [ Elf ("Legolas", Mirkwood) ; Elf ("Elrond", Imladris) ] ~~> true
f4 is_legolas people1 ~~> true
f4 is_from_lorien [ Elf ("Legolas", Mirkwood) ; Elf ("Elrond", Imladris) ] ~~> false
----- 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 : (int × (string list)) list → person list
f5 receives an association list containing pairs of the form (size, list of names).
It returns a list of persons, consisting in Hobbits with the given names for each size.
The order of the hobbits in the list does not matter.
Examples
f5 [] ~~> []
f5 [ (110, []) ] ~~> []
f5 [ (110, [ "Bilbo" ; "Sam" ]) ] ~~> [ Hobbit("Bilbo", 110) ; Hobbit("Sam", 110) ]
f5 [ (110, [ "Bilbo" ; "Sam" ]) ; (83, []) ; (95, [ "Bill"] ) ] ~~> [ Hobbit("Bilbo", 110) ; Hobbit("Sam", 110) ; Hobbit("Bill", 95) ]
----- 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 → (string × (person list)) list
f6 receives a list of persons.
It returns an association list. Each pair in the list is of the form (name, list-of-persons).
It lists, for each name found in the list of persons, the dwarves having that name.
The order of the names and the order of the dwarves in the list does not matter.
Each name must occur only once as a key in the association list.
Examples
f6 [] ~~> []
f6 [ Hobbit("Bilbo", 110) ; Dwarf("Balin", 180) ; Dwarf("Balin", 205) ; Dwarf("Kili", 165) ] ~~> [ ("Balin", [ Dwarf("Balin", 180) ; Dwarf("Balin", 205) ]) ; ("Kili", [ Dwarf("Kili", 165) ]) ]
Too see other examples, use q6_info 12470 ;; in ocaml-top
q6_info 12470 ;;
q6_info 21301 ;;
q6_info 21401 ;;
----- 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 ;;