Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Map.union #6449

Closed
vicuna opened this issue Jun 3, 2014 · 4 comments
Closed

Map.union #6449

vicuna opened this issue Jun 3, 2014 · 4 comments
Assignees
Milestone

Comments

@vicuna
Copy link

vicuna commented Jun 3, 2014

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?

@vicuna
Copy link
Author

vicuna commented Jun 4, 2014

Comment author: @mshinwell

(Same comment as for PR 6450)

@vicuna
Copy link
Author

vicuna commented Jun 4, 2014

Comment author: @alainfrisch

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.

@vicuna
Copy link
Author

vicuna commented Dec 21, 2015

Comment author: @alainfrisch

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).

@vicuna
Copy link
Author

vicuna commented Jan 4, 2016

Comment author: @alainfrisch

Committed to trunk (324ed6b).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants