"ocaml_beginners"::[] unusual behavior of Map.mapi

[Erick Matsen-2]

Hello everyone--


Let's say that we make an ordered int map.

# module OrderedInt =
  struct
      type t = int
      let compare a b = a - b
    end;;
module OrderedInt : sig type t = int val compare : int -> int -> int end

Note that we are using the usual order on the integers.

# module IntMap = Map.Make(OrderedInt);;
let m = List.fold_right (fun k -> IntMap.add k ()) [1;2;module IntMap :
  sig
    type key = OrderedInt.t
    type 'a t = 'a Map.Make(OrderedInt).t

... etc ...

    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
  end

Now we make a unit IntMap with the integers 1 through 4.

# let m = List.fold_right (fun k -> IntMap.add k ()) [1;2;3;4] IntMap.empty;;
val m : unit IntMap.t = <abstr>

Now we use mapi to print the keys:

# let _ = IntMap.mapi (fun i () -> Printf.printf "%d\n" i) m;;
4
3
2
1
- : unit IntMap.t = <abstr>

So it appears that mapi is not giving the keys in increasing order. This is
despite the flollowing from map.mli...

val map: ('a -> 'b) -> 'a t -> 'b t
(** [map f m] returns a map with same domain as [m], where the
   associated value [a] of all bindings of [m] has been
   replaced by the result of the application of [f] to [a].
   The bindings are passed to [f] in increasing order
   with respect to the ordering over the type of the keys. *)

val mapi: (key -> 'a -> 'b) -> 'a t -> 'b t
(** Same as {!Map.S.map}, but the function receives as arguments both the
   key and the associated value for each binding of the map. *)


And that seems to be true in map.ml if arguments are evaluated from left to
right

let rec mapi f = function
    Empty               -> Empty
  | Node(l, v, d, r, h) -> Node(mapi f l, v, f v d, mapi f r, h)

Is that always true?

Or did I just get my signs wrong here?


Thanks,

Erick

[Eric Cooper]

On Mon, Oct 19, 2009 at 11:10:43AM -0700, Erick Matsen wrote:
> So it appears that mapi is not giving the keys in increasing order.

You're right -- this seems to be an evaluation-order bug in map.ml.
This code

    let rec map f = function
        Empty               -> Empty
      | Node(l, v, d, r, h) -> Node(map f l, v, f d, map f r, h)

    let rec mapi f = function
        Empty               -> Empty
      | Node(l, v, d, r, h) -> Node(mapi f l, v, f v d, mapi f r, h)

should be replaced by

    let rec map f = function
        Empty -> Empty
      | Node(l, v, d, r, h) ->
        let l' = map f l in
        let d' = f d in
        let r' = map f r in
        Node (l', v, d', r', h)

    let rec mapi f = function
        Empty -> Empty
      | Node(l, v, d, r, h) ->
        let l' = mapi f l in
        let d' = f v d in
        let r' = mapi f r in
        Node(l', v, d', r', h)

to make the order explicit.

[Ashish Agarwal-2]

> let compare a b = a - b ...> Note that we are using the usual order on the
integers.

No, that would be Pervasives.compare.


On Mon, Oct 19, 2009 at 2:54 PM, Eric Cooper <ecc@...> wrote:

>
>
> On Mon, Oct 19, 2009 at 11:10:43AM -0700, Erick Matsen wrote:
> > So it appears that mapi is not giving the keys in increasing order.
>
> You're right -- this seems to be an evaluation-order bug in map.ml.
> This code
>
> let rec map f = function
> Empty -> Empty
> | Node(l, v, d, r, h) -> Node(map f l, v, f d, map f r, h)
>
> let rec mapi f = function
> Empty -> Empty
> | Node(l, v, d, r, h) -> Node(mapi f l, v, f v d, mapi f r, h)
>
> should be replaced by
>
> let rec map f = function
> Empty -> Empty
> | Node(l, v, d, r, h) ->
> let l' = map f l in
> let d' = f d in
> let r' = map f r in
> Node (l', v, d', r', h)
>
> let rec mapi f = function
> Empty -> Empty
> | Node(l, v, d, r, h) ->
> let l' = mapi f l in
> let d' = f v d in
> let r' = mapi f r in
> Node(l', v, d', r', h)
>
> to make the order explicit.
>
>  
>

[Non-text portions of this message have been removed]

[Erick Matsen-2]

Eh? By "usual order" I mean ... < 1 < 2 < 3 ...

Don't compare a b = a-b and Pervasives.compare give the same order?


Erick

On Mon, Oct 19, 2009 at 12:18 PM, Ashish Agarwal <agarwal1975@...>wrote:

>
>
> > let compare a b = a - b ...> Note that we are using the usual order on
> the
> integers.
>
> No, that would be Pervasives.compare.
>
>
> On Mon, Oct 19, 2009 at 2:54 PM, Eric Cooper <ecc@... <ecc%40cmu.edu>>
> wrote:
>
> >
> >
> > On Mon, Oct 19, 2009 at 11:10:43AM -0700, Erick Matsen wrote:
> > > So it appears that mapi is not giving the keys in increasing order.
> >
> > You're right -- this seems to be an evaluation-order bug in map.ml.
> > This code
> >
> > let rec map f = function
> > Empty -> Empty
> > | Node(l, v, d, r, h) -> Node(map f l, v, f d, map f r, h)
> >
> > let rec mapi f = function
> > Empty -> Empty
> > | Node(l, v, d, r, h) -> Node(mapi f l, v, f v d, mapi f r, h)
> >
> > should be replaced by
> >
> > let rec map f = function
> > Empty -> Empty
> > | Node(l, v, d, r, h) ->
> > let l' = map f l in
> > let d' = f d in
> > let r' = map f r in
> > Node (l', v, d', r', h)
> >
> > let rec mapi f = function
> > Empty -> Empty
> > | Node(l, v, d, r, h) ->
> > let l' = mapi f l in
> > let d' = f v d in
> > let r' = mapi f r in
> > Node(l', v, d', r', h)
> >
> > to make the order explicit.
> >
> >
> >
>
> [Non-text portions of this message have been removed]
>
>  
>

[Non-text portions of this message have been removed]

[Eric Cooper]

BTW, this bug was reported in the ocaml BTS in 2006 -- it's issue #4012.

[Ashish Agarwal-2]

Yes, of course. I was just surprised at your choice. Is there some benefit
to using your definition instead of Pervasives.compare?

On Mon, Oct 19, 2009 at 3:32 PM, Erick Matsen <ematsen@...> wrote:

>
>
> Eh? By "usual order" I mean ... < 1 < 2 < 3 ...
>
> Don't compare a b = a-b and Pervasives.compare give the same order?
>
> Erick
>
> On Mon, Oct 19, 2009 at 12:18 PM, Ashish Agarwal <agarwal1975@...<agarwal1975%40gmail.com>
> >wrote:
>
>
> >
> >
> > > let compare a b = a - b ...> Note that we are using the usual order on
> > the
> > integers.
> >
> > No, that would be Pervasives.compare.
> >
> >
> > On Mon, Oct 19, 2009 at 2:54 PM, Eric Cooper <ecc@...<ecc%40cmu.edu><ecc%
> 40cmu.edu>>
>
> > wrote:
> >
> > >
> > >
> > > On Mon, Oct 19, 2009 at 11:10:43AM -0700, Erick Matsen wrote:
> > > > So it appears that mapi is not giving the keys in increasing order.
> > >
> > > You're right -- this seems to be an evaluation-order bug in map.ml.
> > > This code
> > >
> > > let rec map f = function
> > > Empty -> Empty
> > > | Node(l, v, d, r, h) -> Node(map f l, v, f d, map f r, h)
> > >
> > > let rec mapi f = function
> > > Empty -> Empty
> > > | Node(l, v, d, r, h) -> Node(mapi f l, v, f v d, mapi f r, h)
> > >
> > > should be replaced by
> > >
> > > let rec map f = function
> > > Empty -> Empty
> > > | Node(l, v, d, r, h) ->
> > > let l' = map f l in
> > > let d' = f d in
> > > let r' = map f r in
> > > Node (l', v, d', r', h)
> > >
> > > let rec mapi f = function
> > > Empty -> Empty
> > > | Node(l, v, d, r, h) ->
> > > let l' = mapi f l in
> > > let d' = f v d in
> > > let r' = mapi f r in
> > > Node(l', v, d', r', h)
> > >
> > > to make the order explicit.
> > >
> > >
> > >
> >
> > [Non-text portions of this message have been removed]
> >
> >
> >
>
> [Non-text portions of this message have been removed]
>
>  
>

[Non-text portions of this message have been removed]

[Eric Cooper]

On Mon, Oct 19, 2009 at 06:09:51PM -0400, Ashish Agarwal wrote:
> Yes, of course. I was just surprised at your choice. Is there some benefit
> to using your definition instead of Pervasives.compare?
> On Mon, Oct 19, 2009 at 3:32 PM, Erick Matsen <ematsen@...> wrote:
> > Eh? By "usual order" I mean ... < 1 < 2 < 3 ...
> >
> > Don't compare a b = a-b and Pervasives.compare give the same order?

Using "a - b" instead of "compare a b" doesn't always work:

    # max_int - min_int;;
    - : int = -1
    # compare max_int min_int;;
    - : int = 1

But it's probably slightly faster, since it compiles to a single
instruction rather than a call to the polymorphic comparison function
in the runtime library.