Programmation Fonctionnelle, TD3

Htmligure
Version & licenses
Creative Commons License

Programmation Fonctionnelle, TD3 : Types paramétrés II

Guyslain Naves

Exercice 1 : Fonctions.

Le type des fonctions est un type paramétré, avec deux paramètres :

  1. type ('dom,'im) funct = 'dom -> 'im
  1. Par rapport à 'dom, à quelle catégorie de types paramétrés appartient le type des fonctions ? Par exemple, à quelle catégorie appartient 'dom -> int ?
  2. Et par rapport à 'im, par exemple int -> 'dom ?
  3. Donnez le code des fonctions map et comap. À quoi correspondent map et comap pour les fonctions ?

Exercice 2 : Threads.

Lwt est une librairie permettant de gérer des calculs concurrents. Voici un extrait de l'API :

  1. (** The type of threads computing a result of type ['result]. *)
  2. type 'result t

  3. val return : 'value -> 'value t

  4. val bind : 'value t -> ('value -> 'result t) -> 'result t

  5. (** infix for [bind] *)
  6. val (>>=) : 'value t -> ('value -> 'result t) -> 'result t


  7. val map : ('value -> 'result) -> 'value t -> 'result t

  8. (** infix for [map] *)
  9. val (>|=) : 'value t -> ('value -> 'result) -> 'result t

  10. (** [async f] starts a thread without waiting for the result. *)
  11. val async : (unit -> 'any t) -> unit
  1. À quelle catégorie de type paramétrés appartient Lwt.t ? Pourquoi ?
  2. On se donne :

    1. type event
    2. val mouse_event : unit -> event Lwt.t
    3. val get_position : event -> int * int

    Écrivez un thread qui termine avec pour résultat la position de la souris au prochain événement.

  3. Écrivez un thread qui à chaque événement souris, affiche en sortie standard la position de la souris, indéfiniment.

Exercice 3 : Comparateurs.

Voici l'interface d'un petit module tout simple qui rend de grands services.

  1. type 'elt comparison = 'elt -> 'elt -> int

  2. val int : int comparison
  3. val float : float comparison
  4. val bool : bool comparison
  5. val string : string comparison

  6. val pair : 'fst comparison * 'snd comparison -> ('fst * 'snd) comparison
  7. val list : 'elt comparison -> 'elt list comparison

  8. val comap : ('elt -> 'im) -> 'im comparison -> 'elt comparison

  9. val inverse : 'elt comparison -> 'elt comparison

  10. val min_by : 'elt comparison -> 'elt -> 'elt -> 'elt
  11. val max_by : 'elt comparison -> 'elt -> 'elt -> 'elt

  12. (** [cmp1 <|> cmp2] compares using [cmp1], or when [cmp1] gives
  13. equality, using [cmp2] *)
  14. val (<|>) : 'elt comparison -> 'elt comparison -> 'elt comparison
  1. À quelle catégorie appartient le type 'elt comparison ?
  2. Écrivez des fonctions de comparaisons pour :
    • les paires int * bool,
    • les listes de listes d'entiers (int list) list
    • les paires (float list * int)
  3. Soit le module suivant :

    1. module Person : sig
    2. type t
    3. val get_name : t -> string
    4. val age : t -> int
    5. val id : t -> int
    6. end

    Donnez une fonction pour comparer deux personnes selon leur nom, et en cas d'égalité selon leur âge.

  4. Donnez le code des fonctions inverse et comap.

Exercice 4 : synchronisation.

La librairie standard contient des modules pour manipuler des threads, mais plus bas-niveau que Lwt. Le module Event permet d'établir des communications synchronisées entre threads.

  1. (* from Thread *)
  2. type t

  3. (* creating a thread, a thread computes an application *)
  4. val create : ('arg -> 'res) -> 'arg -> t

  5. (* Waiting for a thread to terminate *)
  6. val join : t -> unit

  7. (* [delay sec] pauses the current thread for [sec] seconds. *)
  8. val delay : float -> unit
  1. (* from Event *)
  2. type 'value channel (* Channel transmitting values of type ['value] *)
  3. type 'value event (* Event with information of type ['value] *)

  4. (* blocking. Synchronises over an event with another thread. *)
  5. val sync : 'value event -> 'value

  6. val send : 'value channel -> 'value -> unit event
  7. val receive : 'value channel -> 'value event

  8. val wrap : 'v event -> ('v -> 't) -> 't event
  1. Écrire un programme créant deux threads. Le premier envoie au second les entiers de 10 à 1 , à une seconde d'intervalle. Le deuxième les affiche. Le programme termine quand les deux threads terminent.
  2. À quelles catégories appartiennent les types channel et event ?
  3. Quel autre nom pourrait-on donner à wrap ?