[Haskell-cafe] Finger Tree without using Monoid
Paterson, Ross
R.Paterson at city.ac.uk
Fri Sep 2 10:32:21 CEST 2011
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
More information about the Haskell-Cafe
mailing list