Consider adding metadata on the balance of the tree to avoid rebalancing during reduction

Discussion about the benchmark results in haskell-perf seems to have spotted a possible issue of the tree getting balanced in the least optimal direction in regards to further folding in some scenarios (e.g., when constructed using fromList). See https://github.com/nikita-volkov/acc/issues/4#issuecomment-976291789.

It is possible that extending the tree with metadata about its balance can solve the issue. However since that involves a tradeoff of having to bookkeep the metadata, it may turn out to be not worthwhile. Also these worst-case scenarios may not even be present in real-world cases. So it needs investigation.

Following is one idea on how the metadata can be represented. I.e., the Int parameter on the Branch constructor:

data NeAcc a
  = Branch
      -- |
      -- Balance.
      -- States in which direction the tree is balanced towards and by how many items.
      -- Determines in which direction the leaf is closest and
      -- ultimately the optimal direction for reduction.
      -- Negative value means balance towards left.
      !Int
      !(NeAcc a)
      !(NeAcc a)
  | Leaf a

nikita-volkov / acc

Consider adding metadata on the balance of the tree to avoid rebalancing during reduction #6