search

benbjohnson / immutable

Immutable collections for Go
MIT License
713 stars 32 forks source link

Key constraint might not be ideal #25

Open anacrolix opened 1 year ago

anacrolix commented 1 year ago

I have a wrapper of immutable that adds sets and some other generic interface stuff. I'm having difficulty mapping it onto v0.4.0 of immutable. I read the PR for the generics, and I think that constraints.Ordered isn't quite right for the key values. I haven't looked into it more, but I suspect it's too strict and that comparable should be possible instead, particularly because the user already has to provide comparer/hasher types in the constructors.

@laher

laher commented 1 year ago

Hi @anacrolix . The problem was that SortedMap requires constraints.Ordered, and there's so much code shared between Map and SortedMap that it was dramatically more straightforward to use constraints.Ordered for both.

Maybe it's not the best approach long-term, but Ben seemed happy with this for now..

Unless there's something I'm missing - maybe I am - I think you'd need to duplicate all the map-related types like Hasher, defaultHasher, MapIterator, mapEntry, mapNode, mapValueNode, mapLeafNode, mapArrayNode, MapBuilder, ... there's a lot of types in there. Hopefully there's some opportunities to avoid some of the duplication, but it's an undertaking - feel free to take it on.

At least you know why it is like it is now :)

benbjohnson commented 1 year ago

I don't have a strong opinion on any of this—mostly because I haven't done much with generics. If anybody has a good solution then I'm open to it but I haven't had time to commit to the immutable project lately.

anacrolix commented 1 year ago

I definitely don't have the time to dedicate to this right now. It's used in the old and obsoleted STM concurrency implementation in anacrolix/dht that I think only gets dredged up because of https://github.com/golang/go/issues/55955.

laher commented 1 year ago

@anacrolix I had a quick experiment with widening the constraint for immutable.Map. Does it help?

anacrolix commented 1 year ago

I will give it a go and report back, thank you @laher !

anacrolix commented 1 year ago

I gave it a spin, it didn't work for the underlying user (although the stm code passed). I think the type can be widened for SortedMap (and any other variants too). Again, because comparers are manually given, the restriction on types belong to those implementations. I'm pretty sure it works for the builtin comparers too, as those use type sets to check for orderable types anyway. Short answer: I think K comparable can be used everywhere in immutable.

laher commented 1 year ago

Short answer: I think K comparable can be used everywhere in immutable.

Good shout - I think it should be OK, just needing a bit of jiggery-pokery on the defaultComparer.

anacrolix commented 1 year ago

Let me know if you do that change, and I'll report back. Thanks @laher