Anonymous | Login | Signup for a new account 2017-09-23 07:37 CEST
 Main | My View | View Issues | Change Log | Roadmap

View Issue Details  Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005170OCamlstandard librarypublic2010-10-25 16:392016-12-07 17:01
Reporterbluestorm
Assigned To
PrioritynormalSeverityfeatureReproducibilityalways
StatusresolvedResolutionsuspended
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 ?
Tagspatch
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