所有权利归论文原作者所有，如果侵权，本人将立刻删除这篇文章。
本文中的代码可以在这里找到https://github.com/hgztheyoung/CopiedCodes/blob/master/ft.hs
论文中的实现见 http://hackage.haskell.org/package/fingertree
这篇博客里的图不错，值得参考
http://www.dalnefre.com/wp/2011/09/finger-tree-a-functional-value-object/
看了[1]里的答案，知道了FingerTree这么个数据结构，十分好奇。
于是从这里[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.
具有一个可结合运算和单位元的类型构成一个Monoid[3]
可结合
(A `mappend` B) `mappend` C = A `mappend` (B `mappend` C)
单位元
A `mappend` mempty = A
mempty `mappend` A = A
具有矩阵乘法和单位矩阵的n*n矩阵构成一个Monoid
具有字符串连接和空字符串的字符串构成一个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.
对monoid做reduction，无论运算顺序如何，总会得到相同的结果 (因为monoid满足结合律)
而对于任意的常量和二元运算做reduction，我们必须指定一种特定的运算顺序(foldr和foldl的区别)
class Reduce f where
reducer :: (a -> b -> b) -> (f a -> b -> b)
reducel :: (b -> a -> b) -> (b -> f a -> b)
这个reducer就是说，输入一个 (a->b->b)的二元运算，就能输出一个(f a->b->b)的函数 (柯里化了，变成这种形式)
可以把这里的f理解成某种泛型的容器，比如list。f a->b->b就是说，给个a类型的容器，比如a的列表，a类型的树等等。
给个b类型的初始值，一般是mempty。就能遍历整个容器，最终得到一个b类型的结果
toList :: (Reduce f) => f a -> [a]
toList s = consbar s [] where
consbar = reducer (:)
toList的签名是说，只要f是实现了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:
只在最后一层存放数据
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.
想要实现O(1)的在两端增加和删除元素，怎么办呢？现在是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.
为了高效的访问两端，把树往中间对折。原来的左右两端成为根，原来的根成为最中间最下方的节点
这里[4]有更多例子。
注意到原来在底端的最左边和最右边，现在在顶端，可以快速访问到。
且越是原来靠近边缘的节点，现在就越接近顶端。在中间的节点可能访问代价会变大。
不过没关系，最多变大一倍，还是O(logN)复杂度。
而且finger tree每向下一层，节点就变得更大。
定义
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 (>-))
-<,-<<,-<<<，只是一些函数名而已。
在这段里头，-<<是 [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)类型了
当然前提是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
入队
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
这一行比较关键，意思是说，这一层的Digit装不下了，就把这个Digit里拿出3个元素，
做个大Node，作为一个元素，插入到下一层去。这保证了FingerTree越往下，节点越大的性质。也就保证了O(logN)复杂度
这个toTree的实现也很有意思，
(<|) :: a -> FingerTree a -> FingerTree a
reducer (<|) 就变成了 f a -> FingerTree a -> FingerTree a
出队
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可以简化成一个 [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把这一层的几个元素，"包装"成Node作为下一层的元素使用
顺便实现让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
