TODO

* Reimplement things a-la HAMT <https://github.com/tibbe/unordered-containers/blob/hamt/Data/HashMap/Base.hs> for the wide fanout, ignoring the hashing stuff naturally.

* Investigate using the new unlifted datatypes:
    https://downloads.haskell.org/~ghc/9.2.1/docs/html/users_guide/exts/primitives.html#unlifted-datatypes

* Consider reintroducing separation of Empty vs other constructors,
  so as to capture the invariant that Branch cannot have Empty
  recursion.  This would allow to remove all the unreachable (findArc Empty)
  cases, which is mainly a hygiene thing, but might could possibly
  help improve codegen/performance.

  Of course, that still doesn't capture the invariants about how
  Arc recurses; however, the only way I can think of to do that
  properly but without introducing massive code complexity, would
  be to switch over to using a GADT to track things.

* Investigate which functions of Data.Trie.Internal should be marked
  as INLINABLE. (And probably re-investigate which public ones are
  marked INLINE.)

* Prove (or at the very least test!) that the Prefix and Mask are
  deterministic regardless of insertion order.

* <https://github.com/wrengr/bytestring-trie/issues/25>

------------------------------------------------------------
Test Coverage:
* Data.Trie:
    adjustBy
    lookupBy: with a function that inspects the second argument.
* Data.Trie.Convenience:
    fromListWith', fromListWithL', lookupWithDefault, insertWith, insertWith', insertWithKey, insertWithKey', adjustWithKey, update, updateWithKey, unionWith, unionWith', intersectWith, intersectWith'
    fromListWith, fromListWithL: use @f@ that evaluates the second argument
* Data.Trie.Internal:
    compare, liftCompare, showsPrec, liftShowsPrec, showTrie, readPrec, readListPrec, (readsPrec), liftReadsPrec, rnf, traverseWithKey, stimes, Foldable(null, toList, minimum, maximum, sum, product), cata_, cata, IsList(toList,fromList), adjust:
        at all
    (>>=):
        a case where the function argument to mergeBy is used.
    mapBy:
        with functions that touches the old value.
    contextualMap, contextualMap', contextualFilterMap, contextualMapBy:
        with functions that touch the trie argument.
    arcPrefix:
        with null string; or better would be to combine with errorLogHead, use assertions, etc
    match_:
        @goJust _ _ _ q (Arc k mv _) | breakMaximalPrefix k q == (_, S.empty, S.empty)@
        One or the other of the two branches on @mv@ will sometimes
        be covered by our test suite, and rarely both will, but
        it'd be better to add some HUnit tests to ensure we always
        cover both.
    mapView:
        Actually, the Nothing case is unreachable for all four use cases. Can/should improve the recursion pattern if we want to get rid of that. ***Must add benchmarks first though!



------------------------------------------------------------
Data.Trie.Internal:
* Verify that the new alterBy_ doesn't make the new alterBy less efficient than the old alterBy.
* Check for the issue about using parameters at multiple recursion levels, as mentioned in the Containers paper. We should force those parameters outside of the recursion, doing so can save big.
* Also check for using their other versions of maskW, which could give 10% speedup!

* Accumulating mapping functions?
* Efficient difference
* Clean up the cruft from development
* make the special handling for epsilons use a consistent style/name for all

------------------------------------------------------------
Data.Trie.BitTwiddle:
* Do benchmarking to compare using (Bits Word8) vs (Bits Int) and elemToNat
* Do benchmarking to see whether the Word8 instances are not worse than Int instances. If Int is better/as-good, see about maybe getting Data.IntMap to switch to using a module like ours and exporting it from base. This would introduce a dependency on a particular base version, but reuse is good.
--- On x86 the time performance is basically the same (trivially worse, within margin of error), memory performance is slightly worse (maybe due to conversions et al). Should be similar on most other architectures, except maybe ARM where Word8 is different than Word16/Word32

------------------------------------------------------------
Data.Trie.ByteStringInternal:
* Write a smart constructor for ByteStrings to ensure good alignment
* Write debugging suite for cross-platform checking

------------------------------------------------------------
Data.Trie.Convenience:
* Try to find a single best implementation of fromList instead of all these variants. Some kind of amortized approximation to sorting which lets us be lazier?
* fromListWith, fromListWithKey?
* insertLookupWithKey, updateLookupWithKey (by some sort of Applicative or State transform? is there a more efficient way without re-engineering the core code?)
* Move elems,keys here from Data.Trie?
* filter (using filterMap), filterWithKey (using mapBy)
* partition, partitionWithKey, mapEither[WithKey] ?
* split, splitLookup ??

------------------------------------------------------------
------------------------------------------------------------
New functions to consider:
* lookup{GT,GE,LT,LE} -- a~la IntMap etc
* splitting versions like lookup{GT,GE,LT,LE}
* alterF -- a~la Data.Map
* BitQueue stuff (cf., Data.Map)??
* lookupIndex -- a~la Data.Map?
* take/drop -- a~la Data.Map, and iterating our current priority-queue stuff

------------------------------------------------------------
------------------------------------------------------------
Other:
* Reconsider a version of Trie that uses natural word size everywhere. Simplest way to maintain invariants is probably to have multiple values stored in each arc (one for each byte). But there might be some other way to do it...

* Get real complexity numbers for the main three functions.

* Reformulate the Binary instance based on discussion on Haskell Cafe re Map