Alternative Dict implementation backed by AVL tree
Elevator pitch
Red-black trees as used in core's Dict require quite a few modifications for rebalancing. Worse; they require quite a few comparisons to do the correct modifications, which is notoriously slow in Elm. AVL trees offer similar worst-case performance characteristics, but in this case, much better insertion performance.
Performance
You can find a little write up on the benchmarks and the methodology on this page.
Using Dict.AVL
Dict.AVL
has the exact same API as core Dict, so using it can be accomplished
by simply doing something like this:
import Dict.AVL as Dict
There is one exception - checking for equality. Since core's Dict is special
cased in elm ecosystem for equality checks, and we can't use this same special
case due to a different internal structure, you'll need to use the
Dict.AVL.eq
function.
import Dict.AVL as Dict
left = Dict.fromList [(0, ()), (1, ())]
right = Dict.fromList [(1, ()), (0, ())]
-- This will return False
left == right
-- This works as expected and returns True
Dict.eq left right