On Wed, 24 Jan 2007, Peter Halacsy wrote:
> Hello,
>
> I've an algorithm (to be exact a Viterbi decoder for HMMs) that uses
>; Map to store some keys.
> Since the algorithm works for all type of keys that can be inserted
> in a map, it's implemented with a functor.
>
>; module Make (State : Map.OrderedType) = struct
>
> ....
>; ...
>
> end
>
>
> Until today I used string lists with limited length. For example a
> used so called string ngrams "a"::"b"::[].
>
> type t = string list
>;
> let rec compare ngram1 ngram2 =
> match (ngram1, ngram2) with
>; ([] , []) -> 0
> | (t::_ , [] ) -> 1
> | ([], t::_) -> -1
> | (t1::h1, t2::h2) -> let c = String.compare t1 t2 in if c != 0
> then c else compare h1 h2
>
>
> let rec chop_right ngram = match ngram with
>; [] -> []
> | l :: [] -> []
> | l :: h -> l :: chop_right h
>
> let add_word ngram word = match ngram with
>; | [] -> word :: []
> | _ -> word :: (chop_right ngram)
>
> for example I read a sentence "a b" and a create two ngrams
>
> let ngram = "start" :: "start" :: [] in
> let ngram2 = add_word ngram "a"
> let ngram2 = add_word ngram "b"
>
>
> Now I noticed the I don't need to chop the last word if the
> comparasion stops after the first 3 elements.
>
> type 'a t = 'a list
>; let gram_compare = String.compare (* could be generalized *)
>
> let empty = []
>
> let add word ngram = word :: ngram
>
> let rec compare ngram1 ngram2 n =
> if n <= 0 then 0 else (* this is NEW *)
> match (ngram1, ngram2) with
>; | (t1::h1, t2::h2) ->
> let c = gram_compare t1 t2 in if c != 0 then c else compare h1 h2
> (pred n)
> | ([] , []) -> 0
> | (t::_ , [] ) -> 1
> | ([], t::_) -> -1
>
> let equal ngram1 ngram2 n =
> (compare ngram1 ngram2 n) = 0
>
>
>; But I can't give this module as a parameter to the functor above.
> Because it has a parameter n that is a running time parameter. I'd
> like to use a Map with a module which has a compare function that has
> a third parameter.
>
> I think there is a very simple solution and I'm tired or stupid.
There are a few solutions:
1) If your n is given only once, when the program is initialized, you can
solve your problem by reading this parameter before applying the functor.
In practice, just place the module that reads n before the other modules
of your program.
let n = ...
let compare n a b = ...
module State =
struct
let compare = compare n
...
end
module M = Make(State)
2) You can use a local module:
let f n =
let module State = struct let compare = compare n ... end in
let module M = Make(State) in
... (* use M, or put the functions into an record or something like that *)
3) Use a global reference to n:
let n_ref = ref None
let set_n i = match !n_ref with None -> n_ref := Some i | _ -> assert false
let get_n () = match !n_ref with None -> assert false | Some i -> i
let compare a b =
let n = get_n () in
...
Martin
--
Martin Jambon
http://martin.jambon.free.fr
.