Advertisement
ezkatkaezgame

Untitled

Aug 6th, 2024
2,786
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
OCaml 4.68 KB | Source Code | 0 0
  1. module type MultiSet = sig
  2.   type 'a t (* the type used to represent the multiset *)
  3.  
  4.   val add_one :
  5.     'a -> 'a t -> 'a t (* add an element, increasing its count by 1 *)
  6.  
  7.   val remove_one : 'a -> 'a t -> 'a t
  8.   (* remove an element, decreasing its count by 1; does nothing if the multiset does not contain the element *)
  9.  
  10.   val count :
  11.     'a ->
  12.     'a t ->
  13.     int (* returns how many times the element is contained in the multiset *)
  14.  
  15.   val any : 'a t -> 'a option
  16.   (* if this multiset is not empty, returns any element that is contained in the multiset as Some x, otherwise returns None *)
  17.  
  18.   val of_list : 'a list -> 'a t
  19.   (* constructs a multiset from a list, where the count of an element is determined by how many times it is contained in the list *)
  20. end
  21.  
  22. module ListMultiSet : MultiSet with type 'a t = 'a list = struct
  23.   type 'a t = 'a list
  24.  
  25.   let add_one x l = x :: l
  26.  
  27.   let remove_one v l =
  28.     let rec impl v l acc =
  29.       match l with
  30.       | [] -> acc
  31.       | x :: xs -> if x = v then impl v [] acc @ xs else impl v xs (x :: acc)
  32.     in
  33.     impl v l []
  34.  
  35.   let count v l =
  36.     let rec impl v l acc =
  37.       match l with
  38.       | [] -> acc
  39.       | x :: xs -> if x = v then impl v xs (acc + 1) else impl v xs acc
  40.     in
  41.     impl v l 0
  42.  
  43.   let any l = match l with [] -> None | x :: xs -> Some x
  44.   let of_list l = l
  45. end
  46.  
  47. module MultiplicityMultiSet : MultiSet with type 'a t = ('a * int) list = struct
  48.   type 'a t = ('a * int) list
  49.  
  50.   let add_one v l =
  51.     let rec impl v l is_added =
  52.       match l with
  53.       | [] -> if is_added then [] else (v, 1) :: []
  54.       | (x, count) :: xs ->
  55.           if x = v then (x, count + 1) :: impl v xs true
  56.           else (x, count) :: impl v xs is_added
  57.     in
  58.     impl v l false
  59.  
  60.   let rec remove_one v l =
  61.     match l with
  62.     | [] -> []
  63.     | (x, count) :: xs ->
  64.         if x = v then
  65.           if count - 1 = 0 then remove_one v xs
  66.           else (x, count - 1) :: remove_one v xs
  67.         else (x, count) :: remove_one v xs
  68.  
  69.   let rec count v l =
  70.     match l with
  71.     | [] -> 0
  72.     | (x, count_var) :: xs -> if x = v then count_var else count v xs
  73.  
  74.   let any l = match l with [] -> None | (x, count) :: xs -> Some x
  75.  
  76.   let of_list l =
  77.     let rec impl l acc =
  78.       match l with [] -> acc | x :: xs -> impl xs (add_one x acc)
  79.     in
  80.     impl l []
  81. end
  82.  
  83. (* MultiSetOperations *)
  84.  
  85. module type MakeMultiSetOperations = functor (BaseMultiSet : MultiSet) -> sig
  86.   include MultiSet with type 'a t = 'a BaseMultiSet.t
  87.  
  88.   val fold : ('a -> int -> 'b -> 'b) -> 'b -> 'a t ->  'b
  89.   val size : 'a t -> int
  90. end
  91.  
  92. (* TODO *)
  93.  
  94. module MultisetOperations : MakeMultiSetOperations =
  95. functor
  96.   (MultiSet : MultiSet)
  97.   ->
  98.   struct
  99.     include MultiSet
  100.  
  101.     let rec remove_all x ms =
  102.       let new_ms = remove_one x ms in
  103.       if count x ms = count x new_ms then new_ms else remove_all x new_ms
  104.  
  105.     let rec fold f acc ms =
  106.       match any ms with
  107.       | None -> acc
  108.       | Some x -> fold f (f x (count x ms) acc) (remove_all x ms)
  109.  
  110.     let size ms =
  111.       let rec impl ms acc =
  112.         match any ms with
  113.         | None -> acc
  114.         | Some x -> impl (remove_all x ms) (acc + count x ms)
  115.       in
  116.       impl ms 0
  117.   end
  118.  
  119. (* EXAMPLES:
  120.  
  121.    Note: for calls to of_list, add_one, remove_one, any, and fold,
  122.    there may be multiple correct answers!
  123.  
  124.    Given the following multiset ms1:
  125.      let ms1 = ListMultiSet.of_list [1; 3; 1; 3; 2]
  126.    Then for each of the following, a correct value could be:
  127.      ms1 = [1; 3; 1; 3; 2]
  128.      ListMultiSet.add_one 4 ms1 = [4; 1; 3; 1; 3; 2]
  129.      ListMultiSet.remove_one 3 ms1 = [1; 1; 3; 2]
  130.      ListMultiSet.count 1 ms1 = 2
  131.      ListMultiSet.count 5 ms1 = 0
  132.      ListMultiSet.any ms1 = Some 1
  133.      ListMultiSet.any [] = None
  134.  
  135.    Given the following multiset ms2:
  136.      let ms2 = MultiplicityMultiSet.of_list ["a"; "c"; "a"; "c"; "b"]
  137.    Then for each of the following, a correct value could be:
  138.      ms2 = [("a", 2); ("b", 1); ("c", 2)]
  139.      MultiplicityMultiSet.add_one "c" ms2 = [("c", 3); ("a", 2); ("b", 1)]
  140.      MultiplicityMultiSet.remove_one "a" ms2 = [("a", 1); ("b", 1); ("c", 2)]
  141.      MultiplicityMultiSet.remove_one "b" ms2 = [("a", 2); ("c", 2)]
  142.      MultiplicityMultiSet.count "a" ms2 = 2
  143.      MultiplicityMultiSet.count "d" ms2 = 0
  144.      MultiplicityMultiSet.any ms2 = Some "a"
  145.      MultiplicityMultiSet.any [] = None
  146.  
  147.    Given the following module M:
  148.      module M = MultiSetOperations (ListMultiSet)
  149.    and the following multiset ms3:
  150.      let ms3 = M.of_list ["a"; "c"; "a"; "c"; "b"]
  151.    Then for each of the following, a correct value could be:
  152.      M.fold (fun x n acc -> (x, n) :: acc) [] ms3 = [("b", 1); ("c", 2); ("a", 2)]
  153.      M.size ms3 = 5
  154. *)
  155.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement