1. 8
  1.  

  2. 2

    Coolest part of this paper is where it mentions finger trees are just one choice in the larger solution space: (from section 10, heading “One less constructor”)

    We believe that an implementation that allows larger Tuples will behave faster in practice, because then there is less administration related to the recursion. The detailed development in this paper opens up for new designs of Finger Trees that can generalize in three dimensions.

    I’d like to read further research about that!

    1. 2

      The time to repacking the Some a and Tuple a would be a constant factor (grows quadratically?) that scales with their sizes and must be taken into account.

      1. 1

        I agree! I’m curious how to measure the trade-offs, any thoughts?

        1. 1

          It depends on the tree size, the operations, the system memory characteristics. It would be nice to have a profiling auto-tuner that automatically morphs from a unboxed packed array to a standard linked list. I guess the finger tree is some where in between these two extremes. Somebody should apply for a research grant for it.

      2. 2

        It’s kind of fascinating how they showed what looks on the surface like a sort of random quirky definition–one to four (or, in their simplified version, three) items here, two or three there–seems to be more-or-less minimal for the attributes they’re going for.