fsharp / fsharp/fslang-suggestions
Support symmetric diff on maps and sets
- Dominant language
- No language data
- Stars
- 373
- Forks
- 21
- PR merge metrics
- No merged PRs in 30d
Description
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
val symmetricDiff: Map<'K,'V> -> Map<'K,'V> -> ('V -> 'V -> bool) -> seq<'K * Choice<'V, 'V, ('V * 'V)>>
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:
val symmetricDiff: Set<'T> -> Set<'T> -> seq<'T * bool>
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:
```
val symmetric_diff : ('k, 'v, 'cmp) t ->
('k, 'v, 'cmp) t ->
data_equal:('v -> 'v -> bool) ->
('k * [ `Left of 'v | `Right of 'v | `Unequal of 'v * 'v ]) list
symmetric_diff t1 t2 ~data_equal returns a list of changes between t1 and t2. It is intended to be efficient in the case where t1 and t2 share a large amount of structure.
```
As an aside, I also notice `Map.merge`:
```
val merge : ('k, 'v1, 'cmp) t ->
('k, 'v2, 'cmp) t ->
f:(key:'k ->
[ `Both of 'v1 * 'v2 | `Left of 'v1 | `Right of 'v2 ] -> 'v3 option) ->
('k, 'v3, 'cmp) t
```
## Affidavit (please submit!)
Please tick this by placing a cross in the box:
* [x] This is not a question (e.g. like one you might ask on [stackoverflow](http://stackoverflow.com)) and I have searched stackoverflow for discussions of this issue
* [x] I have [searched both open and closed suggestions on this site](http://github.com/fsharp/fslang-suggestions/issues) and believe this is not a duplicate
* [x] This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.
Please tick all that apply:
* [ x This is not a breaking change to the F# language design
* [x] I or my company would be willing to help implement and/or test this
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.