Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
    Simon Cruanes
    @c-cube
    Yotam Barnoy
    @bluddy
    heya c-cube! How about a hashmap?
    Simon Cruanes
    @c-cube
    oh hey!
    what about them? :-)
    Simon Cruanes
    @c-cube
    @bluddy is there something CCHashtbl doesn't provide and that cannot be added on top of it?
    Yotam Barnoy
    @bluddy
    It would be nice to have a persistent map with a hashable interface on the functor, so that maps with large or just boxed keys could benefit from being inserted by their hash
    you can build it on top of a regular Map, but it takes some effort and would be nice to have pre-baked
    Simon Cruanes
    @c-cube
    have you looked at CCPersistentHashtbl?
    it's not Map-based, and is not thread-safe, but works very well otherwise
    otoh, indeed, we could do something based on IntMap (with keys being the hash, and leaves being lists of key/value pairs)
    Yotam Barnoy
    @bluddy
    right, that's what i was thinking of.
    is PersistentHashtbl using a diff-array as the backing for a hashtable?
    Simon Cruanes
    @c-cube
    it's based on the same technique as persistent arrays, indeed
    it looks like a regular hashtable but the array of buckets is backed by an 'undo' structure
    in benchmarks, if used linearly, it performs very well
    Yotam Barnoy
    @bluddy
    interesting. i should check it out
    in any case, it would be nice to also have the hashmap data structure
    Simon Cruanes
    @c-cube
    based on Map or patricia trees?
    (also note: weight-balanced trees, hashtrie)
    Yotam Barnoy
    @bluddy
    i think i remember patricia trees vs red-black trees not having that big of a performance difference other than for things like join operations
    Simon Cruanes
    @c-cube
    indeed
    Yotam Barnoy
    @bluddy
    i implemented my own private version on top of Map simply because that's what was available at the time
    Simon Cruanes
    @c-cube
    but what do you need it for? compared to persistentHashtbl or hashtrie?
    (I'm interested anyway, if you want to share your implem)
    Yotam Barnoy
    @bluddy
    oh wait... you have a hashtrie?
    so that's on top of a patricia tree?
    Simon Cruanes
    @c-cube
    it's a kind of HAMT-like structure, yes
    not based on patricia trees
    (so many combinations!)
    Yotam Barnoy
    @bluddy
    OK I didn't even know about HAMT's. Let me read up on it and see if I still want hashmaps :)
    Simon Cruanes
    @c-cube
    there's also a "hamt" library on opam
    Yotam Barnoy
    @bluddy
    ok. pretty cool data structure. Looks better than a hashmap, so I'm good.
    Simon Cruanes
    @c-cube
    test for perf first!
    Yotam Barnoy
    @bluddy
    i will when i get a chance
    great library btw
    Simon Cruanes
    @c-cube
    containers? thanks! :)
    Yotam Barnoy
    @bluddy
    Just ran some quick benchmarks. Hashtries are impressive, at least for lookups: random lookups run almost at the speed of regular hashtables. Random inserts are just a tad faster than regular maps, which on my machine is around 6 times slower than hashtables. I tested with everything specialized for integers, so I'm sure the ratio vs regular maps will improve as bigger types are used. I also like how persistant hashtables are around 1/2 the insert speed of regular hashtables, but around the same lookup speed.
    Simon Cruanes
    @c-cube
    nice!
    also I've added an API for mutating hashtries (batch updates) and my benchmarks show that they lower the allocations
    Simon Cruanes
    @c-cube
    (the benchmarks are in the containers' repo, just in case)
    Yotam Barnoy
    @bluddy
    Am I misremembering, or did you use to have some monadic code in containers? Is it gone?
    Simon Cruanes
    @c-cube
    It's not gone. What are you looking for?
    There are >>= combinators in at least CCList, CCOpt, CCResult, CCRandom
    Yotam Barnoy
    @bluddy
    ah ok, I was looking at CCMap. Wouldn't it make sense to add it to the other data structures?
    Also, the organization of 'core' and 'data' is really confusing. I never remember which is which, and end up going back and forth looking for (and missing) files when I'm seeking them. Would it make sense to just have one directory?
    Simon Cruanes
    @c-cube
    I don't think it makes sense for Map/Set (they are not really monads… or I missed sth)
    no, it doesn't really make sense, sorry ^^
    core/ is the core extension to stdlib
    data/ is an optional collection of data structures
    that are not directly in the stdlib
    Yotam Barnoy
    @bluddy
    Sorry -- didn't mean an actual monadic instance of Map. What I meant was to have a Traversable functor for these data structures, so you could run map_m on them etc. Haven't touched haskell in a while, so these concepts were a bit of a blur.