Consider simplifying the digit implementation?

[turion]

In https://github.com/thalesmg/hallux/blob/master/lib/hallux/internal/digit.ex, the digit type is implemented as having 1 to 4 values. According to https://www.cs.tufts.edu/~nr/cs257/archive/koen-claessen/finger-trees.pdf, you can get rid of the 4-value case. I have a toy implementation doing this: https://github.com/turion/mano

If you want I can submit a PR to hallux deletign the 4-value case.

[thalesmg]

Thanks for bringing this other paper up, I didn't know it! I'll have a look at it.

Just setting some expectations: I must say I'm a bit hesitant of doing a change like this (at least with my limited current knowledge at this moment 🙈 ) because I took for "inspiration" the Data.FingerTree and Data.Seq from Haskell's fingertree and base, respectively. (It's a mostly literal translation from fingertree).

Data.Seq from base is quite heavily used, and I just confirmed it still uses the 4-digit version. So, mimicking them gives me more confidence. I'm curious: do you know perchance why it still uses the 4-digit version? Is there a benefit from using the 3-digit one (aside from less cases to consider in pattern matching)?

I'll read the paper, so I can make a better judgement!

Again, thanks for bringing this up! 🍻

[turion]

The main reason this is not adopted is probably only because finger trees with 4-digits are well-tested since ~20 years by many people, and the version without 4-digits is less than a year old, and "only" submitted as a functional pearl without extensive real-world benchmarks.

[turion]

Is there a benefit from using the 3-digit one (aside from less cases to consider in pattern matching)?

I don't know of any other benefit, in particular no performance improvement.