Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- module type MultiSet = sig
- type 'a t (* the type used to represent the multiset *)
- val add_one :
- 'a -> 'a t -> 'a t (* add an element, increasing its count by 1 *)
- val remove_one : 'a -> 'a t -> 'a t
- (* remove an element, decreasing its count by 1; does nothing if the multiset does not contain the element *)
- val count :
- 'a ->
- 'a t ->
- int (* returns how many times the element is contained in the multiset *)
- val any : 'a t -> 'a option
- (* if this multiset is not empty, returns any element that is contained in the multiset as Some x, otherwise returns None *)
- val of_list : 'a list -> 'a t
- (* constructs a multiset from a list, where the count of an element is determined by how many times it is contained in the list *)
- end
- module ListMultiSet : MultiSet with type 'a t = 'a list = struct
- type 'a t = 'a list
- let add_one x l = x :: l
- let remove_one v l =
- let rec impl v l acc =
- match l with
- | [] -> acc
- | x :: xs -> if x = v then impl v [] acc @ xs else impl v xs (x :: acc)
- in
- impl v l []
- let count v l =
- let rec impl v l acc =
- match l with
- | [] -> acc
- | x :: xs -> if x = v then impl v xs (acc + 1) else impl v xs acc
- in
- impl v l 0
- let any l = match l with [] -> None | x :: xs -> Some x
- let of_list l = l
- end
- module MultiplicityMultiSet : MultiSet with type 'a t = ('a * int) list = struct
- type 'a t = ('a * int) list
- let add_one v l =
- let rec impl v l is_added =
- match l with
- | [] -> if is_added then [] else (v, 1) :: []
- | (x, count) :: xs ->
- if x = v then (x, count + 1) :: impl v xs true
- else (x, count) :: impl v xs is_added
- in
- impl v l false
- let rec remove_one v l =
- match l with
- | [] -> []
- | (x, count) :: xs ->
- if x = v then
- if count - 1 = 0 then remove_one v xs
- else (x, count - 1) :: remove_one v xs
- else (x, count) :: remove_one v xs
- let rec count v l =
- match l with
- | [] -> 0
- | (x, count_var) :: xs -> if x = v then count_var else count v xs
- let any l = match l with [] -> None | (x, count) :: xs -> Some x
- let of_list l =
- let rec impl l acc =
- match l with [] -> acc | x :: xs -> impl xs (add_one x acc)
- in
- impl l []
- end
- (* MultiSetOperations *)
- module type MakeMultiSetOperations = functor (BaseMultiSet : MultiSet) -> sig
- include MultiSet with type 'a t = 'a BaseMultiSet.t
- val fold : ('a -> int -> 'b -> 'b) -> 'b -> 'a t -> 'b
- val size : 'a t -> int
- end
- (* TODO *)
- module MultisetOperations : MakeMultiSetOperations =
- functor
- (MultiSet : MultiSet)
- ->
- struct
- include MultiSet
- let rec remove_all x ms =
- let new_ms = remove_one x ms in
- if count x ms = count x new_ms then new_ms else remove_all x new_ms
- let rec fold f acc ms =
- match any ms with
- | None -> acc
- | Some x -> fold f (f x (count x ms) acc) (remove_all x ms)
- let size ms =
- let rec impl ms acc =
- match any ms with
- | None -> acc
- | Some x -> impl (remove_all x ms) (acc + count x ms)
- in
- impl ms 0
- end
- (* EXAMPLES:
- Note: for calls to of_list, add_one, remove_one, any, and fold,
- there may be multiple correct answers!
- Given the following multiset ms1:
- let ms1 = ListMultiSet.of_list [1; 3; 1; 3; 2]
- Then for each of the following, a correct value could be:
- ms1 = [1; 3; 1; 3; 2]
- ListMultiSet.add_one 4 ms1 = [4; 1; 3; 1; 3; 2]
- ListMultiSet.remove_one 3 ms1 = [1; 1; 3; 2]
- ListMultiSet.count 1 ms1 = 2
- ListMultiSet.count 5 ms1 = 0
- ListMultiSet.any ms1 = Some 1
- ListMultiSet.any [] = None
- Given the following multiset ms2:
- let ms2 = MultiplicityMultiSet.of_list ["a"; "c"; "a"; "c"; "b"]
- Then for each of the following, a correct value could be:
- ms2 = [("a", 2); ("b", 1); ("c", 2)]
- MultiplicityMultiSet.add_one "c" ms2 = [("c", 3); ("a", 2); ("b", 1)]
- MultiplicityMultiSet.remove_one "a" ms2 = [("a", 1); ("b", 1); ("c", 2)]
- MultiplicityMultiSet.remove_one "b" ms2 = [("a", 2); ("c", 2)]
- MultiplicityMultiSet.count "a" ms2 = 2
- MultiplicityMultiSet.count "d" ms2 = 0
- MultiplicityMultiSet.any ms2 = Some "a"
- MultiplicityMultiSet.any [] = None
- Given the following module M:
- module M = MultiSetOperations (ListMultiSet)
- and the following multiset ms3:
- let ms3 = M.of_list ["a"; "c"; "a"; "c"; "b"]
- Then for each of the following, a correct value could be:
- M.fold (fun x n acc -> (x, n) :: acc) [] ms3 = [("b", 1); ("c", 2); ("a", 2)]
- M.size ms3 = 5
- *)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement