所有權(quán)利歸論文原作者所有蜈项，如果侵權(quán)聘殖，本人將立刻刪除這篇文章晨雳。
本文中的代碼可以在這里找到https://github.com/hgztheyoung/CopiedCodes/blob/master/ft.hs
論文中的實(shí)現(xiàn)見 http://hackage.haskell.org/package/fingertree
這篇博客里的圖不錯(cuò)，值得參考
http://www.dalnefre.com/wp/2011/09/finger-tree-a-functional-value-object/
看了[1]里的答案奸腺，知道了FingerTree這么個(gè)數(shù)據(jù)結(jié)構(gòu)餐禁，十分好奇。
于是從這里[2]找了篇論文,抄抄代碼突照，寫寫筆記
2 Preliminaries
2.1 Monoid
class Monoid a where
mempty :: a
mappend :: a->a->a
A type with an associative operation and an identity forms a monoid.
具有一個(gè)可結(jié)合運(yùn)算和單位元的類型構(gòu)成一個(gè)Monoid[3]
可結(jié)合
(A `mappend` B) `mappend` C = A `mappend` (B `mappend` C)
單位元
A `mappend` mempty = A
mempty `mappend` A = A
具有矩陣乘法和單位矩陣的n*n矩陣構(gòu)成一個(gè)Monoid
具有字符串連接和空字符串的字符串構(gòu)成一個(gè)Monoid
2.2 Right and left reductions
A reduction with a monoid yields the same result
however we nest the applications of mappend, but for a reduction with an arbitrary
constant and binary operation we must specify a particular nesting.
對(duì)monoid做reduction帮非，無(wú)論運(yùn)算順序如何，總會(huì)得到相同的結(jié)果 (因?yàn)閙onoid滿足結(jié)合律)
而對(duì)于任意的常量和二元運(yùn)算做reduction，我們必須指定一種特定的運(yùn)算順序(foldr和foldl的區(qū)別)
class Reduce f where
reducer :: (a -> b -> b) -> (f a -> b -> b)
reducel :: (b -> a -> b) -> (b -> f a -> b)
這個(gè)reducer就是說(shuō)末盔，輸入一個(gè) (a->b->b)的二元運(yùn)算筑舅，就能輸出一個(gè)(f a->b->b)的函數(shù) (柯里化了，變成這種形式)
可以把這里的f理解成某種泛型的容器陨舱，比如list翠拣。f a->b->b就是說(shuō)，給個(gè)a類型的容器游盲，比如a的列表误墓，a類型的樹等等。
給個(gè)b類型的初始值背桐，一般是mempty优烧。就能遍歷整個(gè)容器，最終得到一個(gè)b類型的結(jié)果
toList :: (Reduce f) => f a -> [a]
toList s = consbar s [] where
consbar = reducer (:)
toList的簽名是說(shuō)链峭，只要f是實(shí)現(xiàn)了Reduce的容器畦娄，就能從f a類型得到a類型的列表
(:)是 a->[a]->[a]類型，所以 reducer (:)是 f a->[a]->[a]類型弊仪。
3 Simple sequences
As a starting point, consider ordinary 2-3 trees, like the one
below:
只在最后一層存放數(shù)據(jù)
Operations on such trees typically take time logarithmic in the size of the tree,
but for a sequence implementation we would like to add and remove elements from
either end in constant time.
想要實(shí)現(xiàn)O(1)的在兩端增加和刪除元素熙卡，怎么辦呢？現(xiàn)在是O(logN)
3.1 Finger Tree
A structure providing efficient access to nodes of a tree near a distinguished location
is called a finger.To provide efficient access to the ends of a sequence, we wish to place fingers at
the left and right ends of this tree. Imagine taking hold of the end nodes of the
example tree above and lifting them up together.
為了高效的訪問(wèn)兩端励饵，把樹往中間對(duì)折驳癌。原來(lái)的左右兩端成為根，原來(lái)的根成為最中間最下方的節(jié)點(diǎn)
這里[4]有更多例子役听。
注意到原來(lái)在底端的最左邊和最右邊颓鲜，現(xiàn)在在頂端，可以快速訪問(wèn)到典予。
且越是原來(lái)靠近邊緣的節(jié)點(diǎn)甜滨，現(xiàn)在就越接近頂端。在中間的節(jié)點(diǎn)可能訪問(wèn)代價(jià)會(huì)變大瘤袖。
不過(guò)沒(méi)關(guān)系衣摩，最多變大一倍，還是O(logN)復(fù)雜度捂敌。
而且finger tree每向下一層艾扮，節(jié)點(diǎn)就變得更大。
定義
data FingerTree a = Empty
| Single a
| Deep (Digit a) (FingerTree (Node a)) (Digit a)
type Digit a = [a]
data Node a = Node2 a a | Node3 a a a
Before moving on, we instantiate the generic definition of reduction to these
types. Reduction of nodes is trivial:
instance Reduce Node where
reducer (-<) (Node2 a b) z = a -< (b -< z)
reducer (-<) (Node3 a b c) z = a -< (b -< (c -< z))
reducel (>-) z (Node2 b a) = (z >- b) >- a
reducel (>-) z (Node3 c b a) = ((z >- c) >- b) >- a
Reduction of finger trees uses single and double liftings of the binary operation:
instance Reduce FingerTree where
reducer _ Empty z = z
reducer (-<) (Single x) z = x -< z
reducer (-<) (Deep pr m sf ) z = pr -<< (m -<<< (sf -<< z))
where (-<<) = reducer (-<)
(-<<<) = reducer (reducer (-<))
reducel _ z Empty = z
reducel (>-) z (Single x) = z >- x
reducel (>-) z (Deep pr m sf ) = ((z >>- pr) >>>- m) >>- sf
where (>>-) = reducel (>-)
(>>>-) = reducel (reducel (>-))
-<,-<<,-<<<占婉，只是一些函數(shù)名而已泡嘴。
在這段里頭，-<<是 [a]->b->b類型逆济， -<<<是(FingerTree (Node a))->b->b類型
這塊是我瞎猜的
-< :: a -> b -> b
reducer :: (a -> b -> b) -> (f a -> b -> b)
reducer (-<) f0 a -> b -> b
reducer (reducer (-<)) (f1 (f0 a)) -> b -> b
然后f0匹配到Node磕诊，f1匹配到FingerTree填物。所以-<<<就能處理FingerTree(Node a)類型了
當(dāng)然前提是FingerTree和Node都instance了Reduce。
試一下是不是真的能Reduce
*Main> toList Empty
[]
*Main> toList (Single 1)
[1]
*Main> toList (Deep [1,2] Empty [3,4])
[1,2,3,4]
*Main> toList (Deep [1,2] (Single (Node3 3 4 5)) [6,7])
[1,2,3,4,5,6,7]
3.2 Deque operations
入隊(duì)
infixr 5 <|
(<|) :: a -> FingerTree a -> FingerTree a
a <| Empty = Single a
a <| Single b = Deep [a] Empty [b]
a <| Deep [b,c,d,e] m sf = Deep [a,b] (Node3 c d e <| m) sf
a <| Deep pr m sf = Deep ([a] ++ pr) m sf
infixl 5 |>
(|>) :: FingerTree a -> a -> FingerTree a
Empty |> a = Single a
Single b |> a = Deep [b] Empty [a]
Deep pr m [e,d,c,b] |> a = Deep pr (m |> Node3 e d c) [b,a]
Deep pr m sf |> a = Deep pr m (sf ++ [a])
(<||) :: (Reduce f) => f a -> FingerTree a -> FingerTree a
(<||) = reducer (<|)
(||>) :: (Reduce f) => FingerTree a -> f a -> FingerTree a
(||>) = reducel (|>)
toTree :: (Reduce f) => f a -> FingerTree a
toTree s = s <|| Empty
a <| Deep [b,c,d,e] m sf = Deep [a,b] (Node3 c d e <| m) sf
這一行比較關(guān)鍵霎终，意思是說(shuō)滞磺，這一層的Digit裝不下了，就把這個(gè)Digit里拿出3個(gè)元素莱褒，
做個(gè)大Node击困，作為一個(gè)元素，插入到下一層去广凸。這保證了FingerTree越往下阅茶，節(jié)點(diǎn)越大的性質(zhì)。也就保證了O(logN)復(fù)雜度
這個(gè)toTree的實(shí)現(xiàn)也很有意思谅海，
(<|) :: a -> FingerTree a -> FingerTree a
reducer (<|) 就變成了 f a -> FingerTree a -> FingerTree a
出隊(duì)
To deconstruct a sequence, we define a type that expresses a view of the left end
of a sequence as either empty or an element together with the rest of the sequence:
Then we can define separate functions isEmpty, head L , and tail L using the view:
In a lazy language like Haskell, the tail part of the view is not computed unless it
is used. In a strict language, it might be more useful to provide the three separate
functions as primitives.
data ViewL s a = NilL | ConsL a (s a)
data ViewR s a = NilR | ConsR (s a) a
viewL :: FingerTree a -> ViewL FingerTree a
viewL Empty = NilL
viewL (Single x) = ConsL x Empty
viewL (Deep pr m sf) = ConsL (head pr) (deepL (tail pr) m sf)
viewR :: FingerTree a -> ViewR FingerTree a
viewR Empty = NilR
viewR (Single x) = ConsR Empty x
viewR (Deep pr m sf) = ConsR (deepR pr m (init sf)) (last sf)
deepL :: [a] -> FingerTree (Node a) -> Digit a -> FingerTree a
deepL [] m sf =
case viewL m of
NilL -> toTree sf
ConsL a mbar -> Deep (toList a) mbar sf
deepL pr m sf = Deep pr m sf
deepR :: [a] -> FingerTree (Node a) -> Digit a -> FingerTree a
deepR pr m [] =
case viewR m of
NilR -> toTree pr
ConsR mbar a -> Deep pr mbar (toList a)
deepR pr m sf = Deep pr m sf
isEmpty :: FingerTree a -> Bool
isEmpty x = case viewL x of
NilL -> True
ConsL _ _ -> False
headL :: FingerTree a -> a
headL x = case viewL x of ConsL a _ -> a
tailL :: FingerTree a -> FingerTree a
tailL x = case viewL x of ConsL _ x' -> x'
lastR :: FingerTree a -> a
lastR x = case viewR x of ConsR _ a -> a
initR :: FingerTree a -> FingerTree a
initR x = case viewR x of ConsR x' _ -> x'
3.3 Concatenation
The only difficult case is concatenation of two Deep trees.
We can
use the prefix of the first tree as the prefix of the result, and the suffix of the second
tree as the suffix of the result. To combine the rest to make the new middle subtree,
we require a function of type
FingerTree (Node a) → Digit a → Digit a → FingerTree (Node a) →
FingerTree (Node a)
中間的Digit a → Digit a可以簡(jiǎn)化成一個(gè) [a]
app3 :: FingerTree a -> [a] -> FingerTree a -> FingerTree a
app3 Empty ts xs = ts <|| xs
app3 xs ts Empty = xs ||> ts
app3 (Single x) ts xs = x <| (ts <|| xs)
app3 xs ts (Single x) = (xs ||> ts) |> x
app3 (Deep pr1 m1 sf1) ts (Deep pr2 m2 sf2) =
Deep pr1 (app3 m1 (nodes (sf1 ++ ts ++ pr2)) m2) sf2
nodes :: [a] -> [Node a]
nodes [a,b] = [Node2 a b]
nodes [a,b,c] = [Node3 a b c]
nodes [a,b,c,d] = [Node2 a b,Node2 c d]
nodes (a:b:c:xs) = Node3 a b c : nodes xs
(><) :: FingerTree a -> FingerTree a -> FingerTree a
xs >< ys = app3 xs [] ys
Deep pr1 (app3 m1 (nodes (sf1 ++ ts ++ pr2)) m2) sf2
這一句話里脸哀，使用nodes把這一層的幾個(gè)元素，"包裝"成Node作為下一層的元素使用
順便實(shí)現(xiàn)讓FingerTree作為Monoid使用
instance Monoid (FingerTree a) where
mempty = Empty
mappend = (><)
參考鏈接
[1] https://www.zhihu.com/question/32163076
[2] http://www.staff.city.ac.uk/~ross/papers/FingerTree.pdf
[3] https://en.wikipedia.org/wiki/Monoid
[4] http://www.staff.city.ac.uk/~ross/papers/FingerTree/more-trees.html
