Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Repo info
Activity
    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.
    Simon Cruanes
    @c-cube
    ah, I see. The issue is that I would need access to the structure's internals for implementing this kind of stuff (same as for implementing iterators)…
    Yotam Barnoy
    @bluddy
    oh. well, what would be the downside of including and modifying the stdlib implementation files?
    Simon Cruanes
    @c-cube
    1/ license 2/ desynchronisation
    3/ the types would become different
    Yotam Barnoy
    @bluddy
    So... no problem whatsoever. Awesome :smile:
    1. Can't really comment on. 2. not too hard to update with code as it changes, particularly if changes are minor and strategic 3. many of these types are different already since they're using functors
    Simon Cruanes
    @c-cube
    they're not! functors can preserve typing :-)
    Map.Make(String).t is a valid type now
    Yotam Barnoy
    @bluddy
    long-delayed response: thanks for letting me know. Will the iterator proposal help with this if it gets integrated?
    Simon Cruanes
    @c-cube
    I don't even remember -_-
    but maybe, yes, if my PR contains an iterator on the internal elements of Map.S.t
    Yotam Barnoy
    @bluddy
    After writing a small example using Core on discuss.ocaml.org, I've come to realize that Core/Base's decision to put ~f on everything is terrible. It completely destroys the ability to use |> or @@. Please don't ever make the same mistake with Containers, @c-cube. Labels belong on the non-lambdas, like ~init.
    Yotam Barnoy
    @bluddy
    Hmm... or maybe it mostly messes up @@ but not |>
    Simon Cruanes
    @c-cube
    ack.
    Anton Bachin
    @aantron
    yeah, labels become part of the type, so i avoid them for anything public that is meant to be highly-composable in contexts i can't predict