減地圖<'a, int>

Question

兩個地圖我有以下類型：

type Multiset<'a when 'a: comparison> = MSet of Map<'a, int> 

我要聲明的函數這種類型減去2個MSets。

比方說，我有以下兩個多集：

let f = MSet (Map.ofList [("a",1);("b",2);("c",1)]) 
let g = MSet (Map.ofList [("a",1);("b",3);("c",1)]) 

現在我已經試圖創造這個減函數，它需要兩個多集。

let subtract fms sms = 
      match fms with 
      | MSet fs -> match sms with 
          | MSet ss -> 
             let toList ms = Map.fold (fun keys key value -> keys @ [for i = 1 to value do yield key]) [] ms 
             let fromList l = match l with 
                 | [] -> MSet(Map.ofList []) 
                 | x::xs -> MSet(Map.ofList (x::xs |> Seq.countBy id |> Seq.toList)) 
         let sfList = toList fs 
         let ssList = toList ss 
         fromList (List.filter (fun n -> not (List.contains n sfList)) ssList) 

如果我運行：

subtract f g 

它返回：

MSet (map []) 

這是不是我想要的。 g包含一個比f更多的b，所以我想讓它返回：

MSet(map [("b", 1)]) 

我的實現並沒有考慮同一個鍵的多次出現。我不太清楚我如何解決這個問題，所以我得到了想要的功能？

Answer 1

我懷疑你只是把你的觀點顛倒過來，就是這樣。嘗試subtract g f。

也就是說，你的解決方案似乎比它所需要的更復雜。如何通過在第二張圖中減去計數來更新第一張圖中的值，然後刪除非正數呢？

let sub (MSet a) (MSet b) = 
    let bCount key = match Map.tryFind key b with | Some c -> c | None -> 0 
    let positiveCounts, _ = 
     a 
     |> Map.map (fun key value -> value - (bCount key)) 
     |> Map.partition (fun _ value -> value > 0) 
    MSet positiveCounts 

此外，您的實施中的嵌套匹配不需要在那裏。如果你想同時匹配參數，你可以做：

match fms, sms with 
| MSet fs, MSet ss -> ... 

但即使即是矯枉過正 - 你可以只包含參數聲明的模式，就像在我上面的實施。

至於重複鍵 - 在這種情況下，沒有理由擔心：兩個參數都不能有重複鍵（因爲它們都是Map s），並且算法永遠不會產生任何結果。

Answer 2

潛在的問題，在您的other question中也很明顯，似乎是相同鍵的統一。這需要一個等式約束，並且可以通過高級功能Seq.groupBy輕鬆實現。由於比較不是絕對必要的，我建議使用字典，但這種方法也適用於地圖。

給定類型

type MultiSet<'T> = MultiSet of System.Collections.Generic.IDictionary<'T, int> 

和它映射密鑰的幫手，求和它們的值並驗證結果;

let internal mapSum f = 
    Seq.groupBy (fun (KeyValue(k, _)) -> f k) 
    >> Seq.map (fun (k, kvs) -> k, Seq.sumBy (fun (KeyValue(_, v)) -> v) kvs) 
    >> Seq.filter (fun (_, v) -> v > 0) 
    >> dict 
    >> MultiSet 

你的操作變得：

let map f (MultiSet s) = 
    mapSum f s 

let add (MultiSet fms) (MultiSet sms) = 
    Seq.append fms sms 
    |> mapSum id 

let subtract (MultiSet fms) (MultiSet sms) = 
    Seq.map (fun (KeyValue(k, v)) -> 
     System.Collections.Generic.KeyValuePair(k, -v)) sms 
    |> Seq.append fms 
    |> mapSum id 

let f = MultiSet(dict["a", 1; "b", 2; "c", 1]) 
let g = MultiSet(dict["a", 1; "b", 3; "c", 1]) 

subtract f g 
// val it : MultiSet<string> = MultiSet (seq []) 
subtract g f 
// val it : MultiSet<string> = MultiSet (seq [[b, 1] {Key = "b"; 
//             Value = 1;}])