TernaryTrie violates its structural invariant

[robdockins]

The following interaction demonstrates that TernayTrie does not always maintain its structural invariant. I have not yet tracked down the cause. It may be a bug in the statement of the invariant itself, hard to say yet.

$ cabal new-repl edison-core
> :m Data.Edison.Assoc.TernaryTrie
Prelude Data.Edison.Assoc.TernaryTrie> let xs = [([-2],0),([0],0),([-1],0),([-3],0),([1],0),([2],0),([3],0)]
Prelude Data.Edison.Assoc.TernaryTrie> let m  = fromSeq xs
Prelude Data.Edison.Assoc.TernaryTrie> let m' = delete [3] m
Prelude Data.Edison.Assoc.TernaryTrie> structuralInvariant m'
False

[robdockins]

Another possible issue related to this I ran into while running the test suite:

Failed! Falsified (after 76 tests and 39 shrinks):
[([3],0),([1],0),([2],0),([4],0),([-2],0),([0],0),([-1],0)]
### Failure in: 3:finite map tests:7:Ord FM test Data.Edison.Assoc.TernaryTrie:0
src/Data/Edison/Test/Utils.hs:30
Falsified *** Failed! Falsified (after 76 tests and 39 shrinks):
[([3],0),([1],0),([2],0),([4],0),([-2],0),([0],0),([-1],0)]
 76

[Lysxia]

TernaryTrie uses a balancing factor of 6, but according to the following paper which seems the gold standard on the topic, the only valid integer factors are 3 and 4.

Balancing Weight Balanced Trees by Hirai and Yamamoto, 2011 (see Section 4)