=======================================================================================
=== ===
=== 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 : ∀ ' a. (α → int) → α list → int
f1 receives a function g and a list of 'a. It returns an int.
It applies g to every element x in the list and it returns the sum of all such (g x).
Examples
(* Remember that abs is the absolute value. *)
f1 abs [] ~~> 0
f1 abs [ 1 ; 2 ; 3 ] ~~> 6
f1 abs [ -1 ; 2 ; -3 ] ~~> 6
f1 abs [ 0 ; 0 ; 0 ] ~~> 0
----- Question 2 ★ -----
Write a function f2 : ∀ α β γ δ . (α → ((β → α → γ) → β → γ) → δ) → α → δ
Do not try to understand f2's type. You only have to translate the following lambda-term:
f2 is λg.λx.( g x (λf.λy.f y x) )
(You do not need to understand what f2 does either.)
Examples
----- Question 3 ★ -----
Write a function f3 : ∀ α β . (α → β) → β → α option → β
f3 receives a function g, a value y, and an option x.
If x is an empty option (None), f3 returns y.
Otherwise, if x is an option containing a value (Some), it returns g applied to that value.
Examples
f3 (λx . x) 99 None ~~> 99
f3 (λx . x) 99 (Some 40) ~~> 40
f3 (λx . x + 1) 99 (Some 40) ~~> 41
----- Question 4 ★ -----
Open types_bilist.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f4 : ∀ α β . (α → β) → (α, α) bilist → β list
f4 receives a function g and a bilist l.
Every element A x or B x in l is mapped into g x (A and B disappear).
When mapping A elements, if g x raises an exception, then the element is ignored, and the rest of the list is processed.
When mapping B elements, exceptions are not handled, which implies that such exceptions are freely propagated.
Examples
let testg x = if x mod 2 = 0 then x + 1 else raise Switch
f4 (λx . x + 1) [ A 0 ; B 2 ; A 3 ; A 2 ] ~~> [ 1 ; 3 ; 4 ; 3 ]
f4 testg [ A 0 ; B 2 ; A 2 ; A 3 ] ~~> [ 1 ; 3 ; 3 ]
f4 testg [ A 0 ; B 3 ; A 2 ; A 3 ] ~~> raise Switch (* the exception is not caught by f4 *)
----- Question 5 ★ -----
Open types_bilist.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f5 : ∀ α β γ . (α → bool) → (β, α) bilist → bool
f5 receives a predicate f and a bilist l. It returns true if and only if the predicate f is true on all B elements of l.
Examples
let is_even n = (n mod 2 = 0)
f5 is_even [ ] ~~> true
f5 is_even [ A 1 ; A 2 ; A 3 ; B 0 ] ~~> true
f5 is_even [ B 2 ; B 4 ; B 6 ; B 7 ] ~~> false
f5 is_even [ B 2 ; B 4 ; B 6 ; B 8 ] ~~> true
----- Question 6 ★★ -----
Open types_bilist.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f6 : ∀ α β . (α, β) bilist → (α, β) bilist
f6 receives a bilist l.
It returns a new bilist l2 in which the A elements and B elements are kept at the same positions, but the values of A elements are in reversed order.
Examples
f6 [ A 1 ; B 2 ; A 3 ; B 4 ; A 5 ; A 6 ] ~~> [ A 6 ; B 2 ; A 5 ; B 4 ; A 3 ; A 1 ]
----- Question 7 ★★ -----
Open types_bilist.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f7 : ∀ α . (α → bool) → (α, α) bitree → (α, α) bitree
f7 receives a predicate p and a tree.
It returns a new tree which is identical, except that each B leaf which satisfy the predicate p is replaced by an A leaf (with the same value).
Examples
Take a look at test number 400:
q7_info 400 ;; (* A tree with four leaves should be printed (assuming I have the same tree than you). *)
In the expected result, notice that one B leaf has been replaced by an A leaf.
You can directly test your function with
q7_invok f7 400 ;;
Another test: (q7_info 410) has 4 B-leaves, two of which are mapped to A leaves.
----- Question 8 ★★★ -----
Open types_bilist.ml (in pluma: open/ouvrir) and read the type definitions (but do NOT copy it in your program).
Write a function f8 : ∀ α β . (α, β) bitree → (α, β) bitree → ((α, β) bitree × (α, β) bitree) option
f8 receives two trees t1 and t2.
It explores t1 and t2 simultaneously.
If both trees are identical, it returns None.
Otherwise, the trees are different at some point, and f8 must return Some (s1, s2),
where s1 is the first subtree of t1 for which the corresponding subtree s2 in t2 is different,
and s1 or s2 must be a leaf.
This first different subtree is found by depth-first search, left branches first.
Examples
Take a look at test number 5169:
q8_info 5169 ;;
In the expected result, notice that the first difference occur between a B leaf and a node (containing two B leaves).
You can directly test your function with
q8_invok f8 5169 ;;
Another test: (q8_info 1906) shows a difference between two leaves.