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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to