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