Anonymous | Login | Signup for a new account 2016-10-01 00:01 CEST
 Main | My View | View Issues | Change Log | Roadmap

View Issue Details  Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005170OCamlOCaml generalpublic2010-10-25 16:392013-10-07 16:20
Reporterbluestorm
Assigned To
PrioritynormalSeverityfeatureReproducibilityalways
StatusacknowledgedResolutionopen
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.

 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

 Copyright © 2000 - 2011 MantisBT Group