A small standard library extension, string library, and interfaces to various libraries (bigarrays, unix, etc.) BSD license.
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:
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