fsharp / fsharp/fslang-suggestions

Support symmetric diff on maps and sets

Open
#768 15 comments 12 reactions 1 assignee Claimed by @abelbraaksma View on GitHub
approved-in-principle area: library needs rfc
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.