0005170: Order of evaluation of the Map.merge function is unspecified (right-to-left in practice)

View Issue Details [ Jump to Notes ]

[ Issue History ] [ Print ]

Project

Category

View Status

Date Submitted

Last Update

0005170

OCaml

OCaml general

public

2010-10-25 16:39

2012-09-19 14:18

Reporter

bluestorm

Assigned To

Priority

normal

Severity

feature

Reproducibility

always

Status

acknowledged

Resolution

open

Platform

OS Version

Product Version

3.12.0

Target Version

Fixed in Version

Summary

0005170: Order of evaluation of the Map.merge function is unspecified (right-to-left in practice)

Description

The 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 ?

Tags

No tags attached.

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 (manager) 2012-09-19 14:18	till: you're right it's not a bug, but a feature request, and (IMHO) a rather questionable one.

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 =>