3 ms·

> effectively amounts to a O(1) lookup So O(log n) then. We obey gravity around these parts. I presume you are referring to HAMT-like structures ,such as foun

• weavejester 14y ago
  > So O(log n) then. We obey gravity around these parts. Which is of no practical difference to O(1) if log n is always very small. > I presume you are referring to HAMT-like structures... which are by no means unique to Clojure. Of course they're not. My point was that it is not trivial to derive a efficient and useful data structure like a HAMT from Haskell's type system. The data structures in a library like unordered-containers are in practise just as opaque to the developer as the core data structures in Clojure.
  • dons 14y ago
    > as opaque to the developer http://hackage.haskell.org/packages/archive/unordered-containers/0.2.3.0/doc/html/src/Data-HashMap-Base.html#HashMap http://hackage.haskell.org/packages/archive/unordered-contai... This highly optimized data type is defined in 6 lines, easily accessible from the docs.
    • weavejester 14y ago
      No it isn't, at least not in any meaningful way. The type definition itself may be 6 lines, but that doesn't adequately describe the data structure, otherwise there'd be no need for the rest of the library.
• lukev 14y ago
  Actually most Clojure maps are Hashtables, which do have O(1) amortized lookup and insert. Granted, the 'amortized' is important.