undefined | Better HN

0 pointsdons13y ago0 comments

> 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 found in http://hackage.haskell.org/packages/archive/unordered-contai... which are by no means unique to Clojure.

Besides simply having the data type, you still need a good allocator and GC optimized for immutable data, which is where GHC stands alone - http://benchmarksgame.alioth.debian.org/u32q/benchmark.php?t...

0 comments

4 comments · 2 top-level

weavejester13y ago· 2 in thread

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

donsOP13y ago

> as opaque to the developer

http://hackage.haskell.org/packages/archive/unordered-contai...

This highly optimized data type is defined in 6 lines, easily accessible from the docs.

weavejester13y 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.

lukev13y ago

Actually most Clojure maps are Hashtables, which do have O(1) amortized lookup and insert. Granted, the 'amortized' is important.

j / k navigate · click thread line to collapse