2011:11:14:OCaml:Modules:Tas:2

Un article de WikiProg.

Introduction

Ce TP fait suite au TP de la semaine dernière (2011:11:14:OCaml:Modules:Tas:1.)

Ce TP sera à rendre via la procédure habituelle. Le suffixe est heap20111121 donc:

  • l'archive se nomme: login-heap20111121.tar.bz2
  • le répertoire se nomme: login-heap20111121
  • Votre rendu devra contenir un Makefile et un fichier AUTHORS au format habituel.
  • les fichiers suivants au minimum:
    • heap.ml
    • heap.mli
    • index.ml

Le rendu se fera à l'adresse: [1]

Foncteurs

L'objectif est de transformé l'implémentation de tas de la semaine dernière en foncteur dont le paramètre aura l'interface suivante: 

module type MinOrderedType =
sig
  type t
  (* valeur minimal de type t *)
  val min_value : t
  (* la fonction de comparaison classique *)
  val compare : t -> t -> int
end

Le module renvoyé par votre foncteur respectera la spécification suivante: 

module type S =
sig
 
  (* Le type des clefs *)
  type key
 
  (* le type des tas *)
  type 'a t
 
  (* return true if the heap is empty, false otherwise *)
  val is_empty : 'a t -> bool
 
  (* create cap dumm:
   * create a new of capacity cap with a sentinel {min_value,dumm}
   *)
  val create : int -> 'a -> 'a t
 
  (* insert h k v
   * insert {k,v} into heap h
   *)
  val insert : 'a t -> key -> 'a -> unit
 
  (* take_min h
   * extract minimal value (updating the whole heap) and return it
   *)
  val take_min : 'a t -> 'a
 
  (* update h value newkey
   * find pair {oldkey, value}, replace oldkey with newkey and update
   * the heap.
   * If the pair wasn't in the heap, update acts as insert.
   *)
  val update : 'a t -> 'a -> key -> unit
 
end

Le foncteur aura la signature suivante: 

module Make(T : MinOrderedType) : S with type key = T.t

Rendu

Vous devez rendre le module heap.ml respectant la spécification précédante (les bouts de code forme le fichier heap.mli.)

Récupérée de « http://wiki-prog.kh405.net/index.php/2011:11:14:OCaml:Modules:Tas:2 »
Outils personnels