Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0006449OCamlOCaml standard librarypublic2014-06-03 17:462014-06-04 14:08
Reporterfrisch 
Assigned To 
PrioritynormalSeverityfeatureReproducibilityhave not tried
StatusacknowledgedResolutionopen 
PlatformOSOS Version
Product Version 
Target VersionFixed in Version 
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
(0011649)
shinwell (developer)
2014-06-04 09:55

(Same comment as for PR 6450)
(0011652)
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.

- 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


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker