Untitled

ezkatkaezgame

Aug 6th, 2024

2,786

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

OCaml 4.68 KB | Source Code | 0 0

raw download clone embed print report

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
*)

Add Comment

Please, Sign In to add comment