[Haskell-cafe] Finger Tree without using Monoid

[Paterson, Ross]

Xinyu LIU writes:
> I was trying to implement MTF (move-to-front) algorithm, However, neither Array nor List satisfied all aspects.
  Array: Although the random access is O(1), However, move an element to front takes O(N) in average;
  List: Although move to front is O(1), However, random access takes O(N) in average;

> I dig out the paper [1] and find the Finger Tree solution. There is already good Finger Tree implementation in Haskell as Data.Sequence [2] based on [3].

> I wrote a simple version based on the original paper, but avoid using Monoid when augment (or cache) the size of the tree. The idea is to wrap every element as a leaf of node.

Unless I've misread this, I think you're specializing the finger tree to the monoid of natural numbers under addition, as in Section 4.5 of the paper, and also in Data.Sequence.  So one could write move-to-front directly with Data.Sequence as

moveToFront :: Seq a -> Int -> Seq a
moveToFront t i = let (f, b) = splitAt i t in case viewl b of
        x :< b' -> x <| f >< b'
        EmptyL -> t