Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
vicuna opened this issue Oct 25, 2010 · 4 comments

Comments

@vicuna
Copy link

vicuna commented Oct 25, 2010

Original bug ID: 5170
Reporter: bluestorm
Status: resolved (set by @alainfrisch on 2016-12-07T16:01:17Z)
Resolution: suspended
Priority: normal
Severity: feature
Version: 3.12.0
Category: standard library
Tags: patch
Monitored by: @gasche mehdi @ygrek @hcarty

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

@vicuna
Copy link
Author

vicuna commented May 20, 2011

Comment author: till

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.

@vicuna
Copy link
Author

vicuna commented Sep 19, 2012

Comment author: @damiendoligez

till: you're right it's not a bug, but a feature request, and (IMHO) a rather questionable one.

@vicuna
Copy link
Author

vicuna commented Jul 29, 2013

Comment author: @gasche

Note: filter and partition have been modified to use increasing-key evaluation order.

@vicuna
Copy link
Author

vicuna commented Dec 7, 2016

Comment author: @alainfrisch

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant