=======================================================================================
=== ===
=== 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 : ∀ α . (α → int) → α list → α list
f1 receives a function g and a list of 'a. It returns a new list of 'a.
It applies g to every element x in the list. If the result of (g x) is 0, then x is discarded, otherwise x is put in the new list, in the same order.
Examples
let bigger x = if x > 10 then 1 else 0
(* Remember that abs is the absolute value. *)
f1 abs [ ] ~~> []
f1 abs [ 1 ; 2 ; 0 ; 3 ] ~~> [ 1 ; 2 ; 3 ]
f1 bigger [ 1 ; 2 ; 0 ; 3 ] ~~> []
f1 bigger [ 5 ; 15 ; 3 ; 30 ] ~~> [ 15 ; 30 ]
----- 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 λf.( f (λg.λx.g x) (λx.λh.h x) )
(You do not need to understand what f2 does either.)
Examples
----- Question 3 ★ -----
Write a function f3 : ∀ α β . (α → β option) → β → α → β
f3 receives a function g and two values y and x.
It applies g to x. If it returns an empty option (None), the final result must be y.
Otherwise, if g returns an option containing a value (Some), it returns that value.
Examples
f3 (λx . None) 1 2 ~~> 1
f3 (λx . Some x) 1 2 ~~> 2
f3 (λx . Some (x+1)) 1 2 ~~> 3
----- 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 → (α, α) bilist
f4 receives a function g and a bilist l.
Every element A x in l is mapped into A (g x).
Every element B x in l is mapped into B (g x).
If g x raises the exception Switch, then A x is mapped into B x (and conversely with B x becoming A x).
Examples
let testg x = if x mod 2 = 0 then x + 1 else raise Switch
f4 (λx . x + 1) [ A 0 ; B 1 ; A 2 ; A 3 ] ~~> [ A 1 ; B 2 ; A 3 ; A 4 ]
f4 (λx . raise Switch) [ A 0 ; B 1 ; A 2 ; A 3 ] ~~> [ B 0 ; A 1 ; B 2 ; B 3 ]
f4 testg [ A 0 ; B 1 ; A 2 ; A 3 ] ~~> [ A 1 ; A 1 ; A 3 ; B 3 ]
----- 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 : ∀ α β γ . (α → β) → (α, γ) bilist → (β, γ) bilist
From the type of f5, you immediately guess what it does: f5 maps only A elements. B elements are kept as such.
Examples
f5 (λx . x + 1) [ A 1 ; B 5 ; A 2 ; B 6 ] ~~> [ A 2 ; B 5 ; A 3 ; B 6 ]
----- 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 : (int, int) bilist → (int, int) bilist
f6 receives a bilist l. Both A and B contain int values.
It returns a new bilist l2.
In l2, every element (A x) is replaced by (A s), where s is the sum of all A elements strictly before (A x) in l (to the left).
Every element (B x) is replaced by (B s), where s is the sum of all B elements strictly after (B x) in l (to the right).
Examples
f6 [ A 1 ; A 1 ; A 1 ; A 1 ] ~~> [ A 0 ; A 1 ; A 2 ; A 3 ]
f6 [ B 1 ; B 1 ; B 1 ; B 1 ] ~~> [ B 3 ; B 2 ; B 1 ; B 0 ]
f6 [ A 5 ; B 2 ; A 2 ; B 6 ] ~~> [ A 0 ; B 6 ; A 5 ; B 0 ]
f6 [ A 5 ; B 2 ; A 2 ; B 6 ; A 1 ; B 1 ] ~~> [ A 0 ; B 7 ; A 5 ; B 1 ; A 7 ; B 0 ]
----- 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 : ∀ α β γ . (α → β) → (α, γ) bitree → (β, γ) bitree
f7 receives a function f and a tree.
It returns a new tree, where all A leaves have been mapped by f.
Examples
Take a look at test number 1200:
q7_info 1200 ;; (* A tree with four leaves should be printed (assuming I have the same tree than you). *)
In the expected result, notice that only A leaves have been mapped.
You can directly test your function with
q7_invok f7 1200 ;;
----- 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.