Open dsyme opened 5 years ago
There's a rough outline of where the code would have to go here: https://github.com/dotnet/fsharp/compare/master...dsyme:sd?expand=1
I started looking at the implementation but I notice that the implementation for set comparison looks like it allocates a lot. I'm wondering if someone would like to take a look at implementing a much more efficient set/map difference and comparison, which allocates a lot less.
I updated the prototype for set diff'ing to use an imperative 'while' loop - I haven't tested it yet, nor performance-tested it
I suspect for maximum performance (and lowest allocation) the diffing should probably use this signature:
val symmetricDiffWith: set1:Set<'T> -> set2:Set<'T> -> consumer: ('T -> bool -> unit) -> unit
rather than returning a sequence which is then enumerated.
I was thinking of using
seq<'K * Choice<'V, ('V * 'V), 'V,>>
for symmetricDiff.symmetricdiff
for a better symmetry.. This way,
we have Left, Unequal or Right ...
For sets, seq<'T, bool>
and seq<Choice2<'T,'T>>
are isomorphic, but using a boolean doesn't seem the best option... Which side represent true
and false
? We will be googling for doc each time .😬
What about a symmetricDiffFold ?
val symmetricDiffFold: set1:Set<'T> -> set2:Set<'T> -> consumer: ('acc -> Choice2<'T,'T> -> 'acc ) -> seed: 'acc -> 'acc
I was going to propose the same as @thinkbeforecoding regarding sets and seq<Choice2<'T, 'T>>
. But if we do this, then maybe it's more consistent to keep the Map version as Choice<'V, 'V, ('V * 'V)>
rather than make the type parameters symmetric? This way it would be Choice1OfX
for the first source and Choice2OfX
for the second source for both Map and Set.
consumer: ('T -> bool -> unit)
I suggest consumer: ('bool-> 'T -> unit)
, where two T->unit
can be multiplexed.
edit:
and thus, if we're also doing fold
, make consumer: ( 'a1 -> 'a2 -> bool -> 'T -> 'a1*'a2)
Which side represent true and false
Perhaps stick to partition
?
val symmetricDiffFold: set1:Set<'T> -> set2:Set<'T> -> consumer: ('acc -> Choice2<'T,'T> -> 'acc ) -> seed: 'acc -> 'acc
I guess this is why returning seq<...>
is sensible. I'd like to check performance difference between these cases.
BTW one annoying problem with Choice
is that it is an allocation per element of the map....
Isn't it the case with tuples too ?
What about
[<Struct>]
type Side<'t> = Left of 't | Right of 't
?
Isn't it the case with tuples too ?
Yes, though we could make it a struct tuple. FSharp.Core doesn't (yet) contain StructChoice unfortunately
Yes, though we could make it a struct tuple. FSharp.Core doesn't (yet) contain StructChoice unfortunately
It would be odd to have one stdlib function use struct tuples in its signature while the rest of the stdlib uses ref tuples. Maybe it's time to add struct-based variants of all the relevant stdlib functions (eg zip, partition, etc) in dedicated modules?
Hi everyone, quite some time ago we copied the map implementation from F# and extended it with some rather useful functions like choose2 : ('k -> Option<'a> -> Option<'b> -> Option<'c>) -> Map<'k,'a> -> Map<'k, 'b> -> Map<'k, 'c>
which can easily be used to get the symmetric diff as above. These combinators are heavily tested in practice, but as far as i remember there a very limited unit-tests.
Feel free to take whatever you want 😀
Another thing is that the count of the map can easily be maintained (and is in our fork)
Cheers
Forgot to mention: I'd be happy to migrate some of our changes back, and especially alter/choose2/unionWith would be nice to have.
Just let me know it you're willing to give it a try and I'll put together a pull request.
From https://github.com/fsprojects/Fabulous/issues/258#issuecomment-509249457
Watching Yaron Minsky's Strangeloop talk, I notice that F# immutable maps should likely support a "symmetric diff" operation with signature such as
The idea here is that the output sequence contains only elements where the two maps differ, returning the key and a choice between "left map only", "right map only" and "both but different values". Identical elements are not returned.
Sets should also support this with signature like:
where the bool indicates "left set only" or "right set only" and again identical elements are not returned. In both cases pointer equality n the internal trees for the maps/sets is used to avoid re-traversing entire data structures.
The talk also mentions an incrementalizing
diff
operation that relies on a particular incrementalization library for self-adjusting computations.Notes from the OCaml docs:
As an aside, I also notice
Map.merge
:Affidavit (please submit!)
Please tick this by placing a cross in the box:
Please tick all that apply: