In the light of #16 it would be helpful to have a basic benchmark where one can manually, qualitatively, assess what the typical runtimes of basic functions like cons, view_l etc. are.

The Enumerable and Collectable protocols can be implemented for Hallux.Internal.FingerTree, as far as I understand. For some operations (like count on Seq) there are more efficient specific functions in the special cases, but sometimes it would be nice to reuse generic functions when implementing a fingertree with a custom monoid.

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.

The correct spec should be:

@spec view_r(t(val)) :: nil | {t(val), val} when val: value

After reading the original article by Ross & Paterson, I came across the part where they talk about how the performance differs slightly for strict languages as compared to lazy languages. One situation is the head function. In a lazy language, one simply defines head in terms of view_l. But this only has O(1) complexity because the computation of the tail is lazy. In a strict language such as elixir, view_l (

There are two ways out of this:

1. Manual laziness annotations using closures for the :m field in the %Deep{} struct
2. An extra head function that doesn't compute the tail

Option 2. adds some duplicated code and only patches this particular function, but option 1. requires changes in the whole Fingertree module.