containers
containers copied to clipboard
haskell
Add NonEmpty containers, without imbalancing or massive code duplication
There's a number of packages on Hackage providing "non-empty" versions of containers, modeled after https://hackage.haskell.org/package/base/docs/Data-List-NonEmpty.html . There's a variety of use-cases, but perhaps my favorite is that they're needed to "curry" containers: for example, Map (k0, k1) v is isomorphic not to Map k0 (Map k1 v) but to Map k0 (NonEmptyMap k1 v). I like this use-case because it comes from the containers themselves.
Anyways, the problem with the existing implementations is that they tend to just prepend a minimal element to the container. This creates a less efficient, ill-balanced tree. But the alternative of copying the implementation creates a maintain burden. In https://github.com/mokus0/dependent-map/pull/31/files, I think I found an alternative which is the best of both worlds: mostly reused code and no degrade in balancing, namely making the types mutually recur.
For example, here are the types for DMap and NonEmptyDMap:
data DMap k f
= Tip
| Bin' {-# UNPACK #-} !(NonEmptyDMap k f)
pattern Bin s k v l r = Bin' (NonEmptyDMap s k v l r)
data NonEmptyDMap k f where
NonEmptyDMap
:: {- sz -} !Int
-> {- key -} !(k v)
-> {- value -} f v
-> {- left -} !(DMap k f)
-> {- right -} !(DMap k f)
-> NonEmptyDMap k f
DMap is like Maybe NonEmptyDMap but with the unboxed strict field.
Functions are then also written mutually recursively. (Take the exact weird worker wrapper style here with a grain of salt. This me trying to strike a balance between brevity and cargo culting the way the functions were written before.)
makeAdjustWithKey
:: forall k f v
. GCompare k
=> (k v -> f v -> f v)
-> k v
-> ( DMap k f -> DMap k f
, NonEmptyDMap k f -> NonEmptyDMap k f
)
makeAdjustWithKey f k = (k `seq` go, k `seq` go')
where
go :: DMap k f -> DMap k f
go Tip = Tip
go (Bin' ne) = Bin' $! go' ne
go' :: NonEmptyDMap k f -> NonEmptyDMap k f
go' (NonEmptyDMap sx kx x l r) =
case gcompare k kx of
GLT -> NonEmptyDMap sx kx x (go l) r
GGT -> NonEmptyDMap sx kx x l (go r)
GEQ -> NonEmptyDMap sx kx (f kx x) l r
-- | /O(log n)/. Adjust a value at a specific key. When the key is not
-- a member of the map, the original map is returned.
adjustWithKey :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
adjustWithKey f k = fst $ makeAdjustWithKey f k
-- | /O(log n)/. Adjust a value at a specific key. When the key is not
-- a member of the map, the original map is returned.
adjustWithKey :: GCompare k => (k v -> f v -> f v) -> k v -> NonEmptyDMap k f -> NonEmptyDMap k f
adjustWithKey f k = snd $ makeAdjustWithKey f k
One interesting side benefit is that rotations and other internal operations can be less partial. Take rotateL, for example:
rotateL :: k v -> f v -> DMap k f -> NonEmptyDMap k f -> NonEmptyDMap k f
rotateL k x l r@(NonEmptyDMap _ _ _ ly ry)
| sizeE ly < ratio*sizeE ry = singleL k x l r
| otherwise = doubleL k x l r
The non-empty argument proves that at least one left rotation is possible. (The double rotate is still partial.)
As my parenthetical above hints, I haven't yet investigated performance properly; rather my goal was to do just enough work to demonstrate that something like this might be possible. If this sort of refactor looks viable to you, maintainers, I'd be happy to take a stab at doing it for all of containers, along with hunting down any performance issues that arise.
It looks plausible, yes. It'll be a lot of work, though. Do you think you could implement some of the basic operations and get a sense of the performance?
Glad to hear it! I'll start with something like the first commit of the DMap PR, https://github.com/mokus0/dependent-map/pull/31/commits/5985aad23ed339bc8ebda5164cb16a379b0a2b39, to see just the performance impact of just the type change.
It would also be very nice to get a sense of the change in code size in one or two applications. I won't push too hard for that, but it'd be nice.
Are pattern synonyms OK (not too new) to use? I couldn't immediately tell.
We aim for more portability than that. But feel free to use them to get some quick benchmarks!
Sorry for taking a bit; busy at work lately. Here's a branch with just the type change https://github.com/obsidiansystems/containers/tree/non-empty . Hope I'm not jinxing the optimizations being bullish, but know pattern synonyms so far.
Sorry for the delays. It turns out that just as I opened this, I was heading into an especially busy period at work, so I haven't had much time for such open source things. Relatedly, I was being a bit daft and didn't realize you wanted me to run the benchmarks (should have read CONTRIBUTING.md and used common sense...).
Anyways, I did that now on GHC 8.6.3 with -O2, and the type change alone looks alright https://gist.github.com/Ericson2314/58709d0d99e0c0e83ad266701cd71841 . If anything, my type changes seems to have made it slightly faster (did not expect that!). Though I wouldn't also be surprised if there's nothing significant here; I ran them a few hours apart (while doing other things), so CPU temp differences or something might be distorting the results.
If the type change alone looks like a real and worthwhile performance benefit to you, I'd be happy to make the same change for all the containers, and only then sort out whether/how writing and exposing functions for the non-empty types makes sense.
@treeowl light ping :) --- I feel like a hypocrite after I taking a bit to respond my self, but have you had a chance to glance at those benchmarks? Just waiting for the signal to go do the same transformation on the other types.
You probably shouldn't bother with sequences, though. If it's possible to work a trick like that with sequences, it will be much more trouble than it's worth. It would make much more sense to fake non-empty sequences using smart constructors and such.
Right, let me roll back "all the other types" to just sticking to the family of Map, IntMap, Set, and IntSet`.
Er... Are you sure about those Int ones? Make sure they make sense, and make sure they're a separate PR, please. Also, did you ever see the WordMap stuff? It seems to have been abandoned, but it would be very interesting to see where it would go if picked up.
Oh oops completely forget that the Int ones are Patricia trees and also totally different. Nevermind then. The Nil constructor invariant begs for the more conventional newtype IntMap a = IntMap (UnpackingMaybe (NonEmptyIntMap a)), but until sums can be unpacked sadly that's not a pure win.
When do you expect to submit a proposal for non-empty Set and Map to the libraries list? It really shouldn't take long. Just get a good list of applications together.
Sorry I've also been hacking on GHC's build system a bit, spreading myself too thin again. It is indeed not too hard, and I can take a bunch of text from the original issue I opened.
Sorry I took so long. Finally sent in https://mail.haskell.org/pipermail/libraries/2019-April/029537.html
Could someone please summarize how the libraries proposal went?
Also, is there an overview of the proposed API changes?
@sjakobi I recall it was mostly positive feedback? https://github.com/haskell/containers/pull/616 was the implementation. I'm sorry I've never finished it off, I've been busy with many other things.