radix-tree 1.0.0.0 → 1.0.0.1
raw patch · 5 files changed
+199/−123 lines, 5 filesdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- CHANGELOG.md +3/−0
- README.md +67/−0
- radix-tree.cabal +9/−3
- src/Data/RadixNTree/Word8/Lazy.hs +54/−54
- src/Data/RadixNTree/Word8/Strict.hs +66/−66
+ CHANGELOG.md view
@@ -0,0 +1,3 @@+## 1.0.0.0 -- April 2024++* Initial rewrite
+ README.md view
@@ -0,0 +1,67 @@+# radix-tree [](https://hackage.haskell.org/package/radix-tree)+++A Haskell library for [radix trees](https://en.wikipedia.org/wiki/Radix_tree).+++> [!IMPORTANT]+>+> "strict" and "lazy" interfaces within+> [`containers`](https://hackage.haskell.org/package/containers) and+> [`unordered-containers`](https://hackage.haskell.org/package/containers)+> refer to how new values are inserted into the data structures: "strict" means+> they're additionally evaluated to WHNF, "lazy" means they aren't.+> The data structures themselves are spine-strict in either case.+>+> Within this library "strict" and "lazy" refer to spine-strict and spine-lazy+> variants of a given data structure respectively. Evaluating the values before inserting+> them is directly assumed to be user's responsibility.+++Featuring, in order of complexity:++- `Data.Patricia.Word.*`: a+ [PATRICIA tree](https://en.wikipedia.org/w/index.php?title=Radix_tree&oldid=1196786955#Variants).++ The spine-strict variant is effectively identical to+ [`containers#IntMap`](https://hackage.haskell.org/package/containers-0.7/docs/Data-IntMap-Strict.html#t:IntMap).+++- `Data.Zebra.Word`: a space-partitioning tree based on a PATRICIA tree.++ Similar to a+ [`containers#IntSet`](https://hackage.haskell.org/package/containers-0.7/docs/Data-IntSet.html#t:IntSet),+ a `Zebra` stores keys more optimally than a naive `StrictPatricia ()`.+ The approaches are however different:++ - An `IntSet` stores packs of 32/64+ (depending on target platform integer size) adjacent bits together.+ Fully identical feature-wise to regular `IntMap`s otherwise.++ - A `Zebra` partitions the space into black and white zones, effectively storing+ intervals of colors. This allows for fast range fills (see `fillRange`) as well as+ fast lookups of the next key of a particular color (see `lookupL` and `lookupR`).++ Due to the way it is constructed a `Zebra` cannot be spine-lazy.+++- `Data.RadixTree.Word8.*`: a radix tree.++ A general-purpose dictionary type. Asymptotically faster than+ [`containers#Map`](https://hackage.haskell.org/package/containers-0.7/docs/Data-Map-Strict.html)+ (common key prefixes are only scrutinized once) and far more powerful than+ [`unordered-containers#HashMap`](https://hackage.haskell.org/package/unordered-containers-0.2.20/docs/Data-HashMap-Strict.html#t:HashMap)+ (no hash collisions, lookups can fail early, tree can be spine-lazy).++ Note that unlike most dictionaries a `RadixTree` does not have a concrete key type+ and instead uses two key representations: `Feed` (a key broken down to individual bytes)+ and `Build` (a key reconstructed from chunks as they are found within the tree).+ It is thus perfectly legal to mix together different key types, as long as they make+ sense (e.g. a tree of ASCII keys can be treated as a tree of UTF-8 ones at no cost).+++- `Data.Radix1Tree.Word8.*`: a radix tree that cannot store anything at the empty key.++ Exists as a consequence of internal implementation and is convenient for certain+ formats where empty keys are impossible (such as commandline options and INI files).+ Fully identical feature-wise to regular `RadixTree`s otherwise.
radix-tree.cabal view
@@ -1,10 +1,13 @@ name: radix-tree-version: 1.0.0.0+version: 1.0.0.1 category: Data Structures-synopsis: Radix trees.+synopsis: Radix trees description: Radix and PATRICIA trees, both spine-strict and spine-lazy. + See the <https://github.com/sergv/radix-tree/blob/master/README.md README>+ for a brief overview of the data structures included in this package.+ license: BSD3 license-file: LICENSE @@ -17,6 +20,9 @@ homepage: https://github.com/sergv/radix-tree +extra-doc-files: CHANGELOG.md+ README.md+ source-repository head type: git location: https://github.com/sergv/radix-tree.git@@ -91,7 +97,7 @@ hs-source-dirs: src - build-depends: base >= 4.12 && < 5+ build-depends: base >= 4.15 && < 5 , bytestring >= 0.10.4 && < 0.13 , deepseq >= 1.4.3 && < 1.6 , primitive >= 0.7 && < 0.10
src/Data/RadixNTree/Word8/Lazy.hs view
@@ -945,7 +945,7 @@ lookup_ :: (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Maybe a lookup_ step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> go w s $ if w < p@@ -954,7 +954,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = let n' = n + 1 in if n' >= sizeofByteArray arr@@ -990,7 +990,7 @@ find_ :: a -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> a find_ d step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> go w s $ if w < p@@ -999,7 +999,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = let n' = n + 1 in if n' >= sizeofByteArray arr@@ -1037,7 +1037,7 @@ member_ :: (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Bool member_ step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> go w s $ if w < p@@ -1046,7 +1046,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = let n' = n + 1 in if n' >= sizeofByteArray arr@@ -1082,7 +1082,7 @@ subtree_ :: (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> RadixTree a subtree_ step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> go w s $ if w < p@@ -1091,7 +1091,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -1124,7 +1124,7 @@ {-# INLINE prefix_ #-} prefix_ :: (x -> Step Word8 x) -> Word8 -> x -> RadixTree a -> Radix1Tree a-prefix_ step = \w z (RadixTree mx t) ->+prefix_ step = \ !w !z (RadixTree mx t) -> case mx of Nothing -> case t of@@ -1183,7 +1183,7 @@ Seam -> go w s dx Plane i arr -> goarr arr mx dx w s i where- go w s t =+ go !w !s t = case t of Bin p l r -> go w s $ if w < p then l@@ -1195,7 +1195,7 @@ goarr arr mx dx = goarr_ where- goarr_ w s n+ goarr_ w !s n | w == indexByteArray arr n = let !n' = n + 1 in case step s of@@ -1280,7 +1280,7 @@ where getThis = f b arr `fmap'` mx - goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1339,7 +1339,7 @@ let !(# b', arr, a #) = unsafeLookupMinWithKey_ b t in Just $! f b' arr a - go b getR w s t =+ go b getR !w !s t = case t of Bin p l r -> if w < p@@ -1360,7 +1360,7 @@ Nil -> Nothing _ -> getMin (Snoc b arr) dx - goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1410,7 +1410,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustL_ f openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -1424,7 +1424,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1473,7 +1473,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustLWithKey_ f openness step = go Lin where- go b w s t =+ go b !w !s t = case t of Bin p l r -> if w < p@@ -1487,7 +1487,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1538,7 +1538,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustR_ f openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -1552,7 +1552,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1605,7 +1605,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustRWithKey_ f openness step = go Lin where- go b w s t =+ go b !w !s t = case t of Bin p l r -> if w < p@@ -1619,7 +1619,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1667,7 +1667,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a updateL_ f openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -1681,7 +1681,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1734,7 +1734,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a updateLWithKey_ f openness step = go Lin where- go b w s t =+ go b !w !s t = case t of Bin p l r -> if w < p@@ -1748,7 +1748,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1799,7 +1799,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a updateR_ f openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -1813,7 +1813,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1868,7 +1868,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a updateRWithKey_ f openness step = go Lin where- go b w s t =+ go b !w !s t = case t of Bin p l r -> if w < p@@ -1882,7 +1882,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1929,7 +1929,7 @@ takeL_ :: Openness -> (x -> Step Prefix x) -> Prefix -> x -> Radix1Tree a -> Radix1Tree a takeL_ openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -1943,7 +1943,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1988,7 +1988,7 @@ takeR_ :: Openness -> (x -> Step Prefix x) -> Prefix -> x -> Radix1Tree a -> Radix1Tree a takeR_ openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -2002,7 +2002,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -3730,7 +3730,7 @@ insert_ :: a -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a insert_ a step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> join@@ -3742,7 +3742,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -3794,7 +3794,7 @@ :: (a -> a) -> a -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a insertWith_ f a step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> join@@ -3806,7 +3806,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -3856,7 +3856,7 @@ adjust_ :: (a -> a) -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjust_ f step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> t@@ -3865,7 +3865,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -3899,7 +3899,7 @@ delete_ :: (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a delete_ step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> t@@ -3908,7 +3908,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -3947,7 +3947,7 @@ prune_ :: Openness -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a prune_ openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> t@@ -3956,7 +3956,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -3994,7 +3994,7 @@ :: (a -> Maybe a) -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a update_ f step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> t@@ -4003,7 +4003,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -4039,7 +4039,7 @@ -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a alter_ f step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> case f Nothing of@@ -4053,7 +4053,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -4110,7 +4110,7 @@ -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a shape_ f step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> let !(RadixTree my dy) = f (RadixTree Nothing Nil)@@ -4125,7 +4125,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = let n' = n + 1 in if n' >= sizeofByteArray arr@@ -4194,7 +4194,7 @@ -> Word8 -> x -> Radix1Tree a -> (# Radix1Tree a, Radix1Tree a #) splitL_ openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -4212,7 +4212,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -4266,7 +4266,7 @@ -> Word8 -> x -> Radix1Tree a -> (# Radix1Tree a, Maybe a, Radix1Tree a #) splitLookup_ step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -4284,7 +4284,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->
src/Data/RadixNTree/Word8/Strict.hs view
@@ -1018,7 +1018,7 @@ lookup_ :: (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Maybe a lookup_ step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> go w s $ if w < p@@ -1027,7 +1027,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = let n' = n + 1 in if n' >= sizeofByteArray arr@@ -1063,7 +1063,7 @@ find_ :: a -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> a find_ d step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> go w s $ if w < p@@ -1072,7 +1072,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = let n' = n + 1 in if n' >= sizeofByteArray arr@@ -1110,7 +1110,7 @@ member_ :: (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Bool member_ step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> go w s $ if w < p@@ -1119,7 +1119,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = let n' = n + 1 in if n' >= sizeofByteArray arr@@ -1155,7 +1155,7 @@ subtree_ :: (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> RadixTree a subtree_ step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> go w s $ if w < p@@ -1164,7 +1164,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -1197,7 +1197,7 @@ {-# INLINE prefix_ #-} prefix_ :: (x -> Step Word8 x) -> Word8 -> x -> RadixTree a -> Radix1Tree a-prefix_ step = \w z (RadixTree mx t) ->+prefix_ step = \ !w !z (RadixTree mx t) -> case mx of Nothing -> case t of@@ -1256,7 +1256,7 @@ Seam -> go w s dx Plane i arr -> goarr arr mx dx w s i where- go w s t =+ go !w !s t = case t of Bin p l r -> go w s $ if w < p then l@@ -1268,7 +1268,7 @@ goarr arr mx dx = goarr_ where- goarr_ w s n+ goarr_ w !s n | w == indexByteArray arr n = let !n' = n + 1 in case step s of@@ -1353,7 +1353,7 @@ where getThis = f b arr `fmap'` mx - goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1412,7 +1412,7 @@ let !(# b', arr, a #) = unsafeLookupMinWithKey_ b t in Just $! f b' arr a - go b getR w s t =+ go b getR w !s t = case t of Bin p l r -> if w < p@@ -1433,7 +1433,7 @@ Nil -> Nothing _ -> getMin (Snoc b arr) dx - goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1483,7 +1483,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustL_ f openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -1497,7 +1497,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1547,7 +1547,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustL'_ f openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -1561,7 +1561,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1610,7 +1610,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustLWithKey_ f openness step = go Lin where- go b w s t =+ go b !w !s t = case t of Bin p l r -> if w < p@@ -1624,7 +1624,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1679,7 +1679,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustLWithKey'_ f openness step = go Lin where- go b w s t =+ go b !w !s t = case t of Bin p l r -> if w < p@@ -1693,7 +1693,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1744,7 +1744,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustR_ f openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -1758,7 +1758,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1808,7 +1808,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustR'_ f openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -1822,7 +1822,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1875,7 +1875,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustRWithKey_ f openness step = go Lin where- go b w s t =+ go b !w !s t = case t of Bin p l r -> if w < p@@ -1889,7 +1889,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -1943,7 +1943,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjustRWithKey'_ f openness step = go Lin where- go b w s t =+ go b !w !s t = case t of Bin p l r -> if w < p@@ -1957,7 +1957,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -2005,7 +2005,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a updateL_ f openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -2019,7 +2019,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -2072,7 +2072,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a updateLWithKey_ f openness step = go Lin where- go b w s t =+ go b !w !s t = case t of Bin p l r -> if w < p@@ -2086,7 +2086,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -2137,7 +2137,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a updateR_ f openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -2151,7 +2151,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -2206,7 +2206,7 @@ -> Word8 -> x -> Radix1Tree a -> Radix1Tree a updateRWithKey_ f openness step = go Lin where- go b w s t =+ go b !w !s t = case t of Bin p l r -> if w < p@@ -2220,7 +2220,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -2267,7 +2267,7 @@ takeL_ :: Openness -> (x -> Step Prefix x) -> Prefix -> x -> Radix1Tree a -> Radix1Tree a takeL_ openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -2281,7 +2281,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -2326,7 +2326,7 @@ takeR_ :: Openness -> (x -> Step Prefix x) -> Prefix -> x -> Radix1Tree a -> Radix1Tree a takeR_ openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -2340,7 +2340,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -4055,7 +4055,7 @@ insert_ :: a -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a insert_ a step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> join@@ -4067,7 +4067,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -4119,7 +4119,7 @@ :: (a -> a) -> a -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a insertWith_ f a step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> join@@ -4131,7 +4131,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -4187,7 +4187,7 @@ :: (a -> a) -> a -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a insertWith'_ f a step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> join@@ -4199,7 +4199,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -4249,7 +4249,7 @@ adjust_ :: (a -> a) -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjust_ f step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> t@@ -4258,7 +4258,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -4292,7 +4292,7 @@ adjust'_ :: (a -> a) -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a adjust'_ f step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> t@@ -4301,7 +4301,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -4335,7 +4335,7 @@ delete_ :: (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a delete_ step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> t@@ -4344,7 +4344,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -4383,7 +4383,7 @@ prune_ :: Openness -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a prune_ openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> t@@ -4392,7 +4392,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -4430,7 +4430,7 @@ :: (a -> Maybe a) -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a update_ f step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> t@@ -4439,7 +4439,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -4475,7 +4475,7 @@ -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a alter_ f step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> case f Nothing of@@ -4489,7 +4489,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = if n + 1 >= sizeofByteArray arr then case step z of@@ -4546,7 +4546,7 @@ -> (x -> Step Word8 x) -> Word8 -> x -> Radix1Tree a -> Radix1Tree a shape_ f step = go where- go w s t =+ go !w !s t = case t of Bin p l r | beyond p w -> let !(RadixTree my dy) = f (RadixTree Nothing Nil)@@ -4561,7 +4561,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n+ goarr v !z n | v == indexByteArray arr n = let n' = n + 1 in if n' >= sizeofByteArray arr@@ -4636,7 +4636,7 @@ -> Word8 -> x -> Radix1Tree a -> (# Radix1Tree a, Radix1Tree a #) splitL_ openness step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -4654,7 +4654,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->@@ -4714,7 +4714,7 @@ -> Word8 -> x -> Radix1Tree a -> (# Radix1Tree a, Maybe a, Radix1Tree a #) splitLookup_ step = go where- go w s t =+ go !w !s t = case t of Bin p l r -> if w < p@@ -4732,7 +4732,7 @@ Tip arr mx dx -> goarr w s 0 where- goarr v z n =+ goarr v !z n = let n' = n + 1 in case indexByteArray arr n `compare` v of EQ | n' >= sizeofByteArray arr ->