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.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))
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. Exemples:
sort [(-2); 1; 3] (* -> [3; 1; -2] *)
sort ~cmp:(fun x y -> compare (abs x) (abs y)) [(-2); 1; 3] (* -> [3; -2; 1] *)
sort ~rev:true [(-2); 1; 3] (* -> [-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 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
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éments 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.
Random.bool(), Random.int 1000
Array.make 10 'a';;
5 mod 3
(-1) mod 3