减去两个Map <'a,int>的地图

Question

我有以下类型:

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

我想为这种类型声明一个减去两个MSets的函数.

假设我有以下两个Multisets:

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

我现在尝试创建这个带有两个Multisets的减法函数.

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 -> ...

但即便如此也是一种矫枉过正 - 您可以在参数声明中包含模式,就像我上面的实现一样.

至于重复键 - 在这种情况下,没有理由担心:两个参数都没有重复键(因为它们都是Maps),并且算法永远不会产生任何键.