Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005170OCamlstandard librarypublic2010-10-25 16:392016-12-07 17:01
Assigned To 
PlatformOSOS Version
Product Version3.12.0 
Target VersionFixed in Version 
Summary0005170: Order of evaluation of the Map.merge function is unspecified (right-to-left in practice)
DescriptionThe nice new Map.merge function iterates on two streams simultaneously.
While fold, iter and map's implementation enforce a left-to-right (or "increasing key") evaluation order, merge is unspecified :

    let rec merge f s1 s2 =
      match (s1, s2) with ...
      | (Node (l1, v1, d1, r1, h1), _) when h1 >= height s2 ->
          let (l2, d2, r2) = split v1 s2 in
          concat_or_join (merge f l1 l2) v1 (f v1 (Some d1) d2) (merge f r1 r2)
      | ...

It may be nice to enforce its evaluation order so that the function [f] is applied in increasing key order :

    let rec merge f s1 s2 =
      match (s1, s2) with
        (Empty, Empty) -> Empty
      | (Node (l1, v1, d1, r1, h1), _) when h1 >= height s2 ->
          let (l2, d2, r2) = split v1 s2 in
          let l' = merge f l1 l2 in
          let d' = f v1 (Some d1) d2 in
          let r' = merge f r1 r2 in
          concat_or_join l' v1 d' r'
      | (_, Node (l2, v2, d2, r2, h2)) ->
          let (l1, d1, r1) = split v2 s1 in
          let l' = merge f l1 l2 in
          let d' = f v2 d1 (Some d2) in
          let r' = merge f r1 r2 in
          concat_or_join l' v2 d' r'
      | _ ->
          assert false

Note : the predicate-handling functions `for_all`, `exists`, `filter` and `partition` apply their predicates node first, then left branch, then right branch. Should they also be considered for left-right-ification ?
Attached Files

- Relationships

-  Notes
till (reporter)
2011-05-20 15:44

Hmm; am I the only who thinks that this is distinctly not a bug?
I don't really like overspecifying the behaviour of some function; this really locks in the current implementation and potentially makes upgrading/fixing bugs harder.
doligez (administrator)
2012-09-19 14:18

till: you're right it's not a bug, but a feature request, and (IMHO) a rather questionable one.
gasche (developer)
2013-07-29 09:04

Note: filter and partition have been modified to use increasing-key evaluation order.
frisch (developer)
2016-12-07 17:01

Same applies to Map.union. I'm in favor of enforcing the suggested behavior. If anyone still care about it, please submit a Github PR.

- Issue History
Date Modified Username Field Change
2010-10-25 16:39 bluestorm New Issue
2011-05-20 15:03 doligez Status new => acknowledged
2011-05-20 15:44 till Note Added: 0005917
2012-09-06 16:43 doligez Target Version => 4.00.1+dev
2012-09-19 14:18 doligez Note Added: 0008113
2012-09-19 14:18 doligez Severity tweak => feature
2012-09-19 14:18 doligez Target Version 4.00.1+dev =>
2013-07-29 09:04 gasche Note Added: 0009971
2013-10-07 16:20 doligez Tag Attached: patch
2016-12-07 14:49 shinwell Category OCaml general => OCaml standard library
2016-12-07 17:01 frisch Note Added: 0016739
2016-12-07 17:01 frisch Status acknowledged => resolved
2016-12-07 17:01 frisch Resolution open => suspended
2016-12-07 17:01 frisch Assigned To => frisch
2016-12-07 17:01 frisch Assigned To frisch =>
2017-02-23 16:43 doligez Category OCaml standard library => standard library

Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker