Anonymous | Login | Signup for a new account 2017-10-21 06:42 CEST
 Main | My View | View Issues | Change Log | Roadmap

View Issue Details  Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0006449OCamlstandard librarypublic2014-06-03 17:462017-09-24 17:31
Reporterfrisch
Assigned Tofrisch
PrioritynormalSeverityfeatureReproducibilityhave not tried
StatusclosedResolutionfixed
PlatformOSOS Version
Product Version
Target Version4.03.0+dev / +beta1Fixed in Version4.03.0+dev / +beta1
Summary0006449: Map.union
DescriptionThere is a generic merge operation in the Map functor:

val merge:
(key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t
(** [merge f m1 m2] computes a map whose keys is a subset of keys of [m1]
and of [m2]. The presence of each such binding, and the corresponding
value, is determined with the function [f].
@since 3.12.0
*)

A more optimized implementation is possible when the merge function is such that:

merge k (Some x1) None == x1
merge k None (Some x2) == x2
merge k (Some x1) (Some x2) == Some (f k x1 x2)

for some function f.

```    val union:
(key -> 'a -> 'a -> 'a) -> 'a t -> 'a t -> 'a t
(** [union f m1 m2] computes a map whose keys is the union of keys
of [m1] and of [m2].  When the same binding is defined in both
arguments, the function is used to combine them. *)

...

let rec union f s1 s2 =
match (s1, s2) with
| (Empty, s) | (s, Empty) -> s
| (Node (l1, v1, d1, r1, h1), Node (l2, v2, d2, r2, h2)) ->
if h1 >= h2 then
let (l2, d2, r2) = split v1 s2 in
let l = union f l1 l2 and r = union f r1 r2 in
let d =
match d2 with
| None -> d1
| Some d2 -> f v1 d1 d2
in
join l v1 d r
else
let (l1, d1, r1) = split v2 s1 in
let l = union f l1 l2 and r = union f r1 r2 in
let d =
match d1 with
| None -> d2
| Some d1 -> f v2 d1 d2
in
join l v2 d r
```

Contrary to [merge], this [union] function does not need to traverse an operand when the other one is empty.

Any opposition to including this function?
TagsNo tags attached.
Attached Files

 Relationships

 Notes shinwell (developer) 2014-06-04 09:55 (Same comment as for PR 6450) frisch (developer) 2014-06-04 14:08 The story is different here: the provided function cannot be implemented as efficiently without having direct access to the data structure, with the current API. frisch (developer) 2015-12-21 09:25 I'm setting Target Version = 4.03, since this is being discussed in the context of including flambda (Map.union being needed for a time-critical operation). frisch (developer) 2016-01-04 18:41 Committed to trunk (324ed6b).

 Issue History Date Modified Username Field Change 2014-06-03 17:46 frisch New Issue 2014-06-03 22:26 frisch Summary Map.map => Map.union 2014-06-04 09:55 shinwell Note Added: 0011649 2014-06-04 09:55 shinwell Status new => acknowledged 2014-06-04 14:08 frisch Note Added: 0011652 2015-12-21 09:25 frisch Note Added: 0015181 2015-12-21 09:25 frisch Target Version => 4.03.0+dev / +beta1 2016-01-04 18:41 frisch Note Added: 0015222 2016-01-04 18:42 frisch Status acknowledged => resolved 2016-01-04 18:42 frisch Fixed in Version => 4.03.0+dev / +beta1 2016-01-04 18:42 frisch Resolution open => fixed 2016-01-04 18:42 frisch Assigned To => frisch 2017-02-23 16:43 doligez Category OCaml standard library => standard library 2017-09-24 17:31 xleroy Status resolved => closed