Loading ...
Sorry, an error occurred while loading the content.

Map.Make update or add

Expand Messages
  • Jeff Massung
    Am I blind or is a function like Haskell s Data.Map.adjust not present for the Ocaml Map implementation? I hate to think I have to that adding my own naive
    Message 1 of 2 , Oct 24, 2012
    • 0 Attachment
      Am I blind or is a function like Haskell's Data.Map.adjust not present for
      the Ocaml Map implementation? I hate to think I have to that adding my own
      naive implementation of that function would mean O(2 log N)... once to
      search and once to add if not already found.

      I looked at Map.merge, but a cursory test shows that it traverses the
      entire map irregardless of argument ordering, which I had guessed from the
      wording of the documentation (but just wanted to be certain), so it's not
      like I can merge with a singleton map of the one element I'd like to
      add/search for.

      Am I missing something obvious?

      Jeff


      [Non-text portions of this message have been removed]
    • Gabriel Scherer
      O(2 log n) designates the exact same class of functions as O(log n): complexity classes are up to a multiplicative (and additive) constant. Indeed, adjust is
      Message 2 of 2 , Oct 24, 2012
      • 0 Attachment
        O(2 log n) designates the exact same class of functions as O(log n):
        complexity classes are up to a multiplicative (and additive) constant.

        Indeed, "adjust" is not present in the standard library. Among the
        third-party libraries, Batteries provides Map.modify which is similar
        to Data.Map.adjust, and Core has "change" which corresponds to the
        slightly more general Data.Map.alter.

        For reference:
        Data.Map.adjust : Ord k => (a -> a) -> k -> Map k a -> Map k a
        Data.Map.alter : Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
        Batteries: https://github.com/ocaml-batteries-team/batteries-included/blob/master/src/batMap.mli#L97
        Core: https://bitbucket.org/yminsky/ocaml-core/src/8808e3a2571f4c5566957767c1049dba47a71dc9/base/core/lib/core_map_intf.ml?at=default#cl-29

        On Wed, Oct 24, 2012 at 3:50 PM, Jeff Massung <massung@...> wrote:
        > Am I blind or is a function like Haskell's Data.Map.adjust not present for
        > the Ocaml Map implementation? I hate to think I have to that adding my own
        > naive implementation of that function would mean O(2 log N)... once to
        > search and once to add if not already found.
        >
        > I looked at Map.merge, but a cursory test shows that it traverses the
        > entire map irregardless of argument ordering, which I had guessed from the
        > wording of the documentation (but just wanted to be certain), so it's not
        > like I can merge with a singleton map of the one element I'd like to
        > add/search for.
        >
        > Am I missing something obvious?
        >
        > Jeff
        >
        >
        > [Non-text portions of this message have been removed]
        >
        >
        >
        > ------------------------------------
        >
        > Archives up to December 31, 2011 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners
        > The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
        > Attachments are banned and you're asked to be polite, avoid flames etc.Yahoo! Groups Links
        >
        >
        >
      Your message has been successfully submitted and would be delivered to recipients shortly.