58 lines
3.5 KiB
OCaml
58 lines
3.5 KiB
OCaml
|
(* Module de trie *)
|
||
|
|
|
||
|
|
(* type trie
|
||
|
|
le mot est de type 'a, les "caractères" le composant de type 'b
|
||
|
|
*)
|
||
|
|
type ('a,'b) trie
|
||
|
|
|
||
|
|
(******************************************************************************)
|
||
|
|
(* fonction de création d'un nouveau trie *)
|
||
|
|
(* signature : nouveau : *)
|
||
|
|
(* ('a -> 'b list) -> ('b list -> 'a) -> ('a, 'b) trie = <fun> *)
|
||
|
|
(* paramètres : - une fonction de décomposition *)
|
||
|
|
(* mot -> liste de caractères *)
|
||
|
|
(* - une fonction de recomposition *)
|
||
|
|
(* liste de caractères -> mot *)
|
||
|
|
(* résultat : un nouveau trie "vide" *)
|
||
|
|
(******************************************************************************)
|
||
|
|
val nouveau : ('a -> 'b list) -> ('b list -> 'a) -> ('a, 'b) trie
|
||
|
|
|
||
|
|
(******************************************************************************)
|
||
|
|
(* fonction d'appartenance d'un élément à un trie *)
|
||
|
|
(* signature : appartient : 'a -> ('a, 'b) trie -> bool = <fun> *)
|
||
|
|
(* paramètres : - un mot *)
|
||
|
|
(* - un trie *)
|
||
|
|
(* résultat : le résultat booléen du test *)
|
||
|
|
(******************************************************************************)
|
||
|
|
val appartient : 'a -> ('a, 'b) trie -> bool
|
||
|
|
|
||
|
|
(******************************************************************************)
|
||
|
|
(* fonction d'ajout d'un élément dans un trie *)
|
||
|
|
(* signature : ajout : 'a -> ('a, 'b) trie -> ('a, 'b) trie = <fun> *)
|
||
|
|
(* paramètres : - un mot *)
|
||
|
|
(* - un trie *)
|
||
|
|
(* résultat : le trie avec le mot ajouté *)
|
||
|
|
(******************************************************************************)
|
||
|
|
val ajout : 'a -> ('a, 'b) trie -> ('a, 'b) trie
|
||
|
|
|
||
|
|
(******************************************************************************)
|
||
|
|
(* fonction de retrait d'un élément d'un trie *)
|
||
|
|
(* signature : trie_retrait : 'a -> ('a, 'b) trie -> ('a, 'b) trie = <fun> *)
|
||
|
|
(* paramètres : - un mot *)
|
||
|
|
(* - un trie *)
|
||
|
|
(* résultat : le trie avec le mot retiré *)
|
||
|
|
(******************************************************************************)
|
||
|
|
val retrait : 'a -> ('a, 'b) trie -> ('a, 'b) trie
|
||
|
|
|
||
|
|
(******************************************************************************)
|
||
|
|
(* procédure d'affichage d'un trie *)
|
||
|
|
(* signature : affiche : ('a -> unit) -> ('a, 'b) trie -> unit = <fun> *)
|
||
|
|
(* paramètres : - une procédure d'affichage d'un mot *)
|
||
|
|
(* - un trie *)
|
||
|
|
(* résultat : aucun *)
|
||
|
|
(******************************************************************************)
|
||
|
|
val affiche : ('a -> unit) -> ('a, 'b) trie -> unit
|
||
|
|
|
||
|
|
(* Pour les tests *)
|
||
|
|
val trie_sujet : (string,char) trie
|