You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Original bug ID: 6449 Reporter:@alainfrisch Assigned to:@alainfrisch Status: closed (set by @xavierleroy on 2017-09-24T15:31:41Z) Resolution: fixed Priority: normal Severity: feature Target version: 4.03.0+dev / +beta1 Fixed in version: 4.03.0+dev / +beta1 Category: standard library Monitored by:@hcarty
Bug description
There 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?
The text was updated successfully, but these errors were encountered:
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.
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).
Original bug ID: 6449
Reporter: @alainfrisch
Assigned to: @alainfrisch
Status: closed (set by @xavierleroy on 2017-09-24T15:31:41Z)
Resolution: fixed
Priority: normal
Severity: feature
Target version: 4.03.0+dev / +beta1
Fixed in version: 4.03.0+dev / +beta1
Category: standard library
Monitored by: @hcarty
Bug description
There is a generic merge operation in the Map functor:
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.
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?
The text was updated successfully, but these errors were encountered: