Description
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 fDMap 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 kOne 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 rThe 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.
Metadata
Metadata
Assignees
Type
Projects
Milestone
Relationships
Participants
Activity
treeowl commentedon Feb 27, 2019
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?
Ericson2314 commentedon Feb 28, 2019
Glad to hear it! I'll start with something like the first commit of the DMap PR, obsidiansystems/dependent-map@5985aad, to see just the performance impact of just the type change.
treeowl commentedon Feb 28, 2019
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.
Ericson2314 commentedon Mar 3, 2019
Are pattern synonyms OK (not too new) to use? I couldn't immediately tell.
treeowl commentedon Mar 3, 2019
We aim for more portability than that. But feel free to use them to get some quick benchmarks!
Ericson2314 commentedon Mar 9, 2019
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.
treeowl commentedon Mar 9, 2019
So what do your benchmarks show so far?
Ericson2314 commentedon Mar 18, 2019
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.mdand 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.
Ericson2314 commentedon Mar 30, 2019
@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.
treeowl commentedon Mar 30, 2019
I'm generally on board with this approach.
Ericson2314 commentedon Apr 1, 2019
Sweet! I'll convert all the other types and make a PR.
treeowl commentedon Apr 1, 2019
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.
Ericson2314 commentedon Apr 1, 2019
Right, let me roll back "all the other types" to just sticking to the family of
Map,IntMap, Set, andIntSet`.treeowl commentedon Apr 1, 2019
Er... Are you sure about those
Intones? Make sure they make sense, and make sure they're a separate PR, please. Also, did you ever see theWordMapstuff? It seems to have been abandoned, but it would be very interesting to see where it would go if picked up.12 remaining items