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