Use mergewith for merging dicts of sets

[gdalle]

Linking to #33 (comment) so that we may close the PR first and get rid of union! afterwards

[adrhill]

To keep everything in one place, the proposition in the comment is for a function mergewith, which does:

julia> d1 = Dict(1 => Set([1, 2, 3]), 2 => Set([3, 4, 5]))
Dict{Symbol, Set{Int64}} with 2 entries:
  1 => Set([2, 3, 1])
  2 => Set([5, 4, 3])

julia> d2 = Dict(2 => Set([5, 6, 7]), 3 => Set([8, 9, 10]))
Dict{Symbol, Set{Int64}} with 2 entries:
  2 => Set([5, 6, 7])
  3 => Set([10, 9, 8])

julia> mergewith(union, d1, d2)
Dict{Symbol, Set{Int64}} with 3 entries:
  1 => Set([2, 3, 1])
  2 => Set([5, 4, 6, 7, 3])
  3 => Set([10, 9, 8])

HessianTracer already has two such functions:

• additive_merge
• distributive_merge

The proposed mergewith function looks egal to additive_merge:

julia> d1 = Dict(UInt(1) => Set([1, 2, 3]), UInt(2) => Set([3, 4, 5]))
Dict{UInt64, Set{Int64}} with 2 entries:
  0x0000000000000002 => Set([5, 4, 3])
  0x0000000000000001 => Set([2, 3, 1])

julia> d2 = Dict(UInt(2) => Set([5, 6, 7]), UInt(3) => Set([8, 9, 10]))
Dict{UInt64, Set{Int64}} with 2 entries:
  0x0000000000000002 => Set([5, 6, 7])
  0x0000000000000003 => Set([10, 9, 8])

julia> SparseConnectivityTracer.additive_merge(HessianTracer(d1), HessianTracer(d2))
HessianTracer{Set{Int64}}(
  2 => (5, 4, 6, 7, 3),
  3 => (10, 9, 8),
  1 => (2, 3, 1),
)

[adrhill]

Closing this for now, but PRs increasing the performance of additive_merge and distributive_merge are obviously welcome.

The two functions are named after their analogous operations on polynomials. In the given example, d1 corresponds to the polynomial $d_1 = x_1(x_1 + x_2 + x_3) + x_2(x_3+x_4+x_5)$ and d2 to $d_2 = x_2(x_5 + x_6 + x_7) + x_3(x_8 + x_9+x_{10})$.
additive_merge corresponds to $d_1 + d_2$, distributive_merge corresponds to $d_1 \cdot d_2$.

The implementation of this is closely related to #34.
It will probably make sense to have multiple methods depending on the used set types.
But we need benchmarks first.

[gdalle]

I'm not proposing a new function, I'm pointing out it's part of Base:

help?> mergewith
search: mergewith mergewith!

  mergewith(combine, d::AbstractDict, others::AbstractDict...)
  mergewith(combine)
  merge(combine, d::AbstractDict, others::AbstractDict...)


  Construct a merged collection from the given collections. If necessary, the
  types of the resulting collection will be promoted to accommodate the types
  of the merged collections. Values with the same key will be combined using
  the combiner function. The curried form mergewith(combine) returns the
  function (args...) -> mergewith(combine, args...).

[adrhill]

TIL! Could this be used for distributive_merge as well?

[gdalle]

idk