Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] 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
(0005917)
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.
(0008113)
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.
(0009971)
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
Powered by Mantis Bugtracker