On souhaite écrire une fonction liste_aleatoire qui prend en argument une fonction sans argument generateur et qui renvoie une liste de valeurs de type 'a. La fonction generateur est appelée un nombre de fois aléatoire pour tirer au hasard chacun des éléments de la liste. La longueur de la liste est elle aussi tirée au hasard: avec une chance sur deux il s'agit de la liste vide, avec une chance sur quatre elle est de longueur 1, avec une chance sur 8 elle est de longueur 2, etc.
liste_aleatoire?liste_aleatoire.(* 1 : le type est (unit -> 'a) -> 'a list *)
let liste_aleatoire gen =
let rec res () =
if Random.bool () then [] else gen () :: res ()
in res ()
let _ = liste_aleatoire (fun () -> Random.int 1000)
On définit les types suivants
type booleen = Vrai | Faux
type lazybool = booleen Lazy.t
Définissez la fonction ou : lazybool -> lazybool -> lazybool qui calcule le "ou logique" de deux booléens paresseux. La fonction renvoie un booléen paresseux. Il y a plusieurs approches possibles, toutes seront acceptées, tant que le second booléen n'est pas systématiquement forcé.
Combien de "!" sont affichés par le code suivant?
let vrai = lazy (print_string "!"; Vrai)
let faux = lazy (print_string "!"; Faux)
let _ = Lazy.force (ou (ou faux faux) (ou vrai vrai))
type booleen = Vrai | Faux
type lazybool = booleen Lazy.t
let ou b1 b2 =
if Lazy.force b1 = Vrai then lazy(Vrai) else b2
let vrai = lazy (print_string "!"; Vrai)
let faux = lazy (print_string "!"; Faux)
let _ = Lazy.force (ou (ou faux faux) (ou vrai vrai))
let () = print_newline ()
let ou b1 b2 =
lazy(if Lazy.force b1 = Vrai then Vrai else Lazy.force b2)
let vrai = lazy (print_string "!"; Vrai)
let faux = lazy (print_string "!"; Faux)
let _ = Lazy.force (ou (ou faux faux) (ou vrai vrai))
let () = print_newline ()
List.sort (4 points)¶On rappelle que la fonction List.sort : ('a->'a->int)-> 'a list -> 'a list
prend comme premier argument une fonction permettant de comparer deux éléments de la liste.
On utilise souvent la comparaison "par défaut" d'OCaml donnée par la fonction compare.
Définissez une fonction sort : ?cmp:('a -> 'a -> int) -> ?rev:bool -> 'a list -> 'a list
qui prend deux arguments optionnels cmp et rev, le premier étant la fonction de comparaison, et le second un booléen, qui, s'il est à vrai, inverser l'ordre de tri.
let sort ?(cmp=compare) ?(rev=false) l =
let cmp = if rev then cmp else (fun x y -> cmp y x) in
List.sort cmp l
let _ = sort [(-2); 1; 3]
let _ = sort ~cmp:(fun x y -> compare (abs x) (abs y)) [(-2); 1; 3]
let _ = sort ~rev:true [(-2); 1; 3]
Un multi-ensemble est un "ensemble avec répétitions", autrement dit "une liste non ordonnée". Par exemple, le multi-ensemble $\{\,\{a,a,b,c,c,c\}\,\}$ est le même que $\{\,\{a,b,c,a,c,c\}\,\}$, et son cardinal vaut 6.
module type MULTISET = sig
type 'a mset
val empty : 'a mset
val singleton : ....
val union : 'a mset -> 'a mset -> 'a mset
val intersection : ...
val cardinal : ....
val appartient : 'a -> 'a mset -> bool
val est_inclus : 'a mset -> 'a mset -> bool
val map : ('a -> 'b) -> 'a mset -> 'b mset
end
[(a,2);(b,1);(c,3)]. Afin d'avoir unicité de la représentation, on impose que les clés (ici a,b,c) sont triées en ordre croissant; on impose de plus que les valeurs (ici 2,1,3) sont des entiers strictement positifs. Complétez la définition du module ci-dessous.module Multiset : MULTISET = struct
type 'a mset = ('a * int) list
...
end
module type MULTISET = sig
type 'a mset
val empty : 'a mset
val singleton : 'a -> 'a mset
val union : 'a mset -> 'a mset -> 'a mset
val intersection : 'a mset -> 'a mset -> 'a mset
val cardinal : 'a mset -> int
val map : ('a -> 'b) -> 'a mset -> 'b mset
end
module Multiset : MULTISET = struct
type 'a mset = ('a * int) list
let empty = []
let singleton a = [(a,1)]
let rec union ms1 ms2 = match ms1, ms2 with
| [], _ -> ms2
| _, [] -> ms1
| (a, n) :: ms11 , (b, _) :: _ when a < b -> (a, n) :: union ms11 ms2
| (a, _) :: _ , (b, m) :: ms22 when a > b -> (b, m) :: union ms1 ms22
| (a, n) :: ms11, (b, m) :: ms22 -> (a, n + m) :: union ms11 ms22
let rec intersection ms1 ms2 = match ms1, ms2 with
| [], _ | _, [] -> []
| (a, _) :: ms11 , (b, _):: _ when a < b -> intersection ms11 ms2
| (a, _) :: _ , (b, _):: _ when a > b -> intersection ms2 ms1
| (a, n) :: ms11, (b, m) :: ms22 -> (a, min n m) :: intersection ms11 ms22
let cardinal ms = List.fold_left (fun n (_, m) -> n+m) 0 ms
let map f ms = List.fold_left (fun acc (a, n) -> union acc [(f a, n)]) empty ms
end
On rappelle qu'une file est une structure de données qui contient des éléments ordonnés par ordre d'ajout dans la file. Lorsqu'on retire un élément de la file, c'est l'élément le plus ancien qui est retiré. La capacité d'une file est le nombre maximal d'éléments qu'elle peut contenir simultanément. Une file de capacité $k$ finie peut être représentée par la donnée de trois informations:
tab de taille klen compris entre 0 et k indiquant le nombre d'élément dans la filenext indiquant l'indice auquel on stockera dans le tableau le prochain élément ajouté.Intuitivement, quand on ajoute un élément on incrémente next de 1 modulo k, et quand on enlève un élément, on décrémente len.
En suivant cette approche, définissez un module BoundedFifo qui aura la signature suivante
module type BOUNDEDFIFO = sig
type 'a fifo
exception Empty
exception Full
val create : int -> 'a fifo
val push : 'a -> 'a fifo -> unit
val pop : 'a fifo -> 'a
val len : 'a fifo -> int
end
Indication: En OCaml il n'y a pas de valeur "par défaut" pour un tableau. La fonction create devra donc renvoyer une "file vierge" qui contient uniquement l'information de la capacité $k$, et c'est premier push qui allouera le tableau en le remplissant entièrement de la valeur passée en argument.
module type BOUNDEDFIFO = sig
type 'a fifo
exception Empty
exception Full
val create : int -> 'a fifo
val push : 'a -> 'a fifo -> unit
val pop : 'a fifo -> 'a
val len : 'a fifo -> int
end
module BoundedFifo : BOUNDEDFIFO = struct
type 'a fifo = {
mutable tab : 'a array option;
mutable len : int;
mutable next : int;
capacity : int
}
exception Empty
exception Full
let create k = { tab = None; len = 0; next = 0; capacity = k}
let push a fifo = match fifo with
| {tab = None} -> begin
fifo.tab <- Some (Array.make fifo.capacity a);
fifo.len <- 1;
fifo.next <- 1;
end
| {len; capacity} when len = capacity -> raise Full
| {tab = Some tab; next; len; capacity} -> begin
tab.(next) <- a;
fifo.next <- (next + 1) mod capacity;
fifo.len <- len + 1
end
let pop fifo = match fifo with
| {tab = None} | {len=0} -> raise Empty
| {tab = Some tab; next; len; capacity} -> begin
fifo.len <- len - 1;
tab.((capacity + next - len - 1) mod capacity)
end
let len {len} = len
end