Finger Trees (Part 2. Operations)

The article will consist of 3 parts:
Finger Trees (Part 1. Introduction)
Finger Trees (Part 2. Operations)
Finger trees (part 3. Application)

Finger Trees as Sequences

In the first part of the article, we looked at finger trees as a promising structure as non-mutable sequences. And they learned how to create finger trees. I want to note, learned to create so that it became impossible in principle to build the wrong trees. Now our task is to learn how to work with finger trees as with sequences: learn how to attach to the beginning and end of a sequence, learn how to easily separate sequences from both ends, and also connect several trees into one.

The motivation for developing this strange structure is the desire to have a tree as a sequence, which would allow you to quickly have access to the end and the beginning. In this section, we will implant operations that allow us to see sequences in finger trees.

Attach to start and end

Let's start by adding a finger tree to the beginning. Ideally, we would like to add an element simply by adding it to the tree prefix. But this will only work for trees that have 1, 2 or 3 elements in their prefix, and absolutely will not work for a finger tree, which has 4 elements in its prefix. Just because the prefix can not be longer than four. To avoid the prefix of length 5, we wrap 3 of these 5 elements, wrap them in Node using the Branch3 construction, and attach them to a deeper finger tree:

 --  <|    .      :   infixr 5 <| (<|) :: a -> FingerTree a -> FingerTree a --   #1.      ,  1  x <| Empty = Single x --   #2:   ,     1 -- ,         'Affix a'  x <| Single y = Deep [x] Empty [y] --  :      4 ,   --   2      ,    --           ,     x <| Deep [a, b, c, d] deeper suffix = Deep [x, a] (node <| deeper) suffix where node = Branch3 bcd --  :       x <| tree = tree { prefix = affixPrepend x $ prefix tree } 

All this we can apply for joining the right, because we have the same access to the right end of the tree, as well as to the left end:

 infixl 5 |> (|>) :: FingerTree a -> a -> FingerTree a Empty |> y = Single y Single x |> y = Deep [x] Empty [y] Deep prefix deeper [a, b, c, d] |> y = Deep prefix (deeper |> node) [d, y] where node = Branch3 abc tree |> y = tree { suffix = affixAppend y $ suffix tree } 

Now we can build a finger tree easily using joining to the beginning and to the end of it.

 > let empty = Empty > 't' <| empty |> 'x' |> 'y' |> 'z' |> 'w' |> 'm' Deep {prefix = One 't', deeper = Single (Branch3 'x' 'y' 'z'), suffix = Two 'w' 'm'} 

Although we implemented the joining to the beginning and the end of the finger tree, it seems that we did not get much in terms of efficiency because of the trees, because if we are unlucky and the tree already has many prefixes of length 4, we should go deep into the tree to add items. As a result, the worst case of adding to the beginning and end is O(lg n) , where n is the number of elements.
Until the worst case gets better, the conversion for the typical case is improved. In most cases of adding, the user attaches many elements to the string, each time only saving the new modified tree and discarding the old one. Let us analyze this case, assuming that we transform m additions into a series
Analyzing the asymptomatics of this case, we note that first comes the non-recursive part, which is constant in time. The initial tree is small ( Empty or Single x ), or if we can immediately add an element, modifying the prefix, the addition takes O(1) time. The recursive case (when the affix is ​​4 in length) is more complicated to calculate. However, when we add to an affix of length 4, we instantly rebalance a tree with an affix of length 2. So, we know that the next operation will be instantaneous and take a constant time, and there is no need to go to another level. From this we can deduce that no more than half of the join operations do not need a recursive case of switching to the second level of the finger tree. And after each recursive case, there must be at least one non-recursive one. Similar logic applies to the second layer: we know that only a quarter of operations can be possible to go deep into the third layer. Continuing this logic, the nth layer of the finger tree can be visited only in one of every 2n-1 actions. So, the total time for all m additions in the worst case will be
T=m+1/2m+1/4m+1/8m+⋯ ,
However, even if we assume an infinite number of layers, the time will be finite - 2m (which is easy to see if you notice the formula of a geometric series). In the real case, O(m) time will be spent for m additions, and although in the worst case the time of one operation will be O(lg n) , where n is the number of elements in the tree, the amortized time for this case will be only O(1) for any addition from the beginning or from the end.

View (First and Last)

In the previous paragraph, we looked at the implementation of the join operation from the beginning (|>) and from the end (<|) elements in a sequence (sequence) based on a finger tree. But, in addition to adding elements, there is an urgent need to look at them and delete them. Both of these operations are based on a more universal operation — a preview, which we will implement below.
We need a viewing operation in 2 versions: a view on the right ( viewr ) and a view on the left ( viewl ). Each of them takes one element from the end (left or right, respectively) and returns the element along with the rest of the finger tree.
In order to make it clearer, we need the equivalent of the following function for lists:

 --    ,   `Maybe`, --        ,  . listViewL :: [a] -> Maybe (a, [a]) listViewL [] = Nothing listViewL (x:xs) = Just (x, xs) 

The simplest implementation for a finger tree might look like this:

 --       --   Maybe (a, FingerTree a). data View a = Nil | View a (FingerTree a) deriving Show viewl :: FingerTree a -> View a viewl Empty = Nil --     viewl (Single x) = View x Empty --    viewl (Deep prefix deeper suffix) = View first $ Deep (fromList rest) deeper suffix where --  ,       , --      first:rest = toList prefix 

We can even test the implementation, how to work with an empty tree:

 > viewl empty Nil > viewl exampleTree View 't' (Deep {prefix = One 'h', deeper = Deep {prefix = Two (Branch2 'i' 's') (Branch2 'i' 's'), deeper = Empty, suffix = Two (Branch3 'n' 'o' 't') (Branch2 'a' 't')}, suffix = Three 'r' 'e' 'e'}) 

And, although this design seems to work, the implementation has a serious leak. Do you see her?
The following code block shows the problem:

 > let View _ rest = viewl exampleTree > viewl rest --     1  4 ! 

When we write this case for viewl, which deals with the constructor Deep , we simply remove the element from the left prefix. But this will work only for as long as we have at least 1 element, but as soon as we want to pull the element from the inside, the tree will be wrong. In the block described above, we tried to use viewl to create a finger tree, which would contain 0 elements in the prefix, which of course illegally and instantly causes an error.
Therefore, we need to take into account this case, and count the number of elements in the prefix of the finger tree. If there is only one element, we cannot simply remove it; instead, we must use the viewl for a deeper finger tree to get the Node a branch. This Node a contains 2 or 3 values, so we can safely pull out one prefix element, and instead replace it with the prefix contained in Node a , so the transformation always guarantees the size of the affix between 1 and 4 elements. The following implementation of viewl works for all cases (we still use the View a data structure described earlier):

 --      viewl :: FingerTree a -> View a viewl Empty = Nil --     viewl (Single x) = View x Empty --    --    Deep   --       --    ,     viewl (Deep [x] deeper suffix) = View x rest where rest = --    : case viewl deeper of --          View node rest' -> --      Deep (fromList $ toList node) rest' suffix --           --      --        Nil -> case suffix of [x] -> Single x [x, y] -> Deep [x] Empty [y] --   2 ,    ,  --   .  --  -         [x, y, z] -> Deep [x, y] Empty [z] [x, y, z, w] -> Deep [x, y, z] Empty [w] -- ,     Deep --          viewl (Deep prefix deeper suffix) = View first $ Deep (fromList rest) deeper suffix where first:rest = toList prefix 

With this new viewl implementation, our crash test will work perfectly

 > let View _ rest = viewl exampleTree > viewl rest View 'h' (Deep {prefix = Two 'i' 's', deeper = Deep {prefix = One (Branch2 'i' 's'), deeper = Empty, suffix = Two (Branch3 'n' 'o' 't') (Branch2 'a' 't')}, suffix = Three 'r' 'e' 'e'}) 

The right viewl , viewr implemented almost completely the same, only using prefixes instead of suffixes and vice versa.

 viewr :: FingerTree a -> View a viewr Empty = Nil viewr (Single x) = View x Empty viewr (Deep prefix deeper [x]) = View x rest where rest = case viewr deeper of --    ,   View node rest' -> Deep prefix rest' (fromList $ toList node) --    ,      Nil -> case prefix of [x] -> Single x [x, y] -> Deep [x] Empty [y] [x, y, z] -> Deep [x] Empty [y, z] [x, y, z, w] -> Deep [x] Empty [y, z, w] viewr (Deep prefix deeper suffix) = View suffixLast $ Deep prefix deeper (fromList suffixInit) where suffixLast = last $ toList suffix suffixInit = init $ toList suffix 

We use the function in the same way as viewl , we can view the end of the sequence

 > viewr exampleTree View 'e' (Deep {prefix = Two 't' 'h', deeper = Deep {prefix = Two (Branch2 'i' 's') (Branch2 'i' 's'), deeper = Empty, suffix = Two (Branch3 'n' 'o' 't') (Branch2 'a' 't')}, suffix = Two 'r' 'e'}) 

Since we have the necessary primitives to view, we can easily create the remaining few functions for finger trees, similar to head , tail , last , init , and null for lists

 treeHead :: FingerTree a -> a treeHead tree = case viewl tree of Nil -> error "no elements in tree" View x _ -> x treeTail :: FingerTree a -> FingerTree a treeTail tree = case viewl tree of Nil -> error "no elements in tree" View _ xs -> xs treeLast :: FingerTree a -> a treeLast tree = case viewr tree of Nil -> error "no elements in tree" View x _ -> x treeInit :: FingerTree a -> FingerTree a treeInit tree = case viewr tree of Nil -> error "no elements in tree" View _ xs -> xs isEmpty :: FingerTree a -> Bool isEmpty tree = case viewl tree of Nil -> True _ -> False 

And in particular, this allows us to easily convert lists into finger trees and vice versa:

 --       . instance IsList (FingerTree a) where type Item (FingerTree a) = a toList tree = case viewl tree of Nil -> [] View x xs -> x : toList xs fromList = foldr (<|) Empty 

The use of finger trees has become much simpler:

 > [1..6] :: FingerTree Int Deep {prefix = Two 1 2, deeper = Single (Branch3 3 4 5), suffix = One 6} 

Concatenation

Another operation that we can implement using finger trees is concatenation / join. For this, we have all the necessary functions for a simple connection, since we can recursively browse and attach elements. The easiest implementations will be:

 --     >< . (><) :: FingerTree a -> FingerTree a -> FingerTree a left >< Empty = left left >< right = let View first rest = viewl right in (left |> first) >< rest 

And although this implementation works well, this implementation is very slow. In terms of asymptotic time, this is the same as using the toList function to decompose a finger tree, merge two lists, and convert back to a finger tree. We have previously shown that |> takes O(1) amortized time, but this procedure will be done O(m) times, where m is the number of elements in the right tree, which we pass to the function >< . As a result, the total time O(m) - linearly depends on the number of elements that we attach.
We will try to create much better by utilizing the structure of the finger tree. Before doing this, we need a helper function called nodes, which can convert the list of elements into a list of nodes of elements:

 nodes :: [a] -> [Node a] nodes xs = case xs of [] -> error "not enough elements for nodes" [x] -> error "not enough elements for nodes" [x, y] -> [Branch2 xy] [x, y, z] -> [Branch3 xyz] x:y:rest -> Branch2 xy : nodes rest 

For every 2 elements of the original list, the nodes will contain only one in the new list of nodes. In the order of connection, an odd number of elements, nodes will contain Branch3 on the left side. As a result, we are sure that the function of nodes, if given a list of elements, always create a list of n/2 nodes. This we need in the future.
Next, we will redefine concatenation in terms of a slightly strange operator, which we call “connect with the middle” ( concatWithMiddle ). The connector takes two FingerTree a values ​​for the connection, as well as a list of items between the two trees.
Implementing the same connection using a mid-connector is a trivial task — just use an empty list as an additional argument.

 (><) :: FingerTree a -> FingerTree a -> FingerTree a left >< right = concatWithMiddle left [] right concatWithMiddle :: FingerTree a -> [a] -> FingerTree a -> FingerTree a concatWithMiddle = unimplemented where unimplemented = error "Soon to come!" 

Things are concatWithMiddle - implement concatWithMiddle . We need a special case if we have trees with constructors Empty or Single . In these cases, the compound is reduced to O(1) addition.
Here we keep a list of additional elements in the middle also in order to use several attachments at both ends.
In addition to the boundary cases, we must take care of the main case, when both trees have the constructor Deep . Here we will also return Deep along with:
prefix equal to the prefix of the left tree,
suffix equal to the suffix of the right tree
deep inner tree equal to recursive call concatWithMiddle
We must also remember the suffix of the left tree and the prefix of the right tree. By combining with the middle elements passed to concatWithMiddle . While deep finger trees store Node a nodes instead of values, we use the helper function to create a list of nodes that we pass recursively to the concatWithMiddle function. It certainly sounds weird, but it should be readable from code:

 concatWithMiddle :: FingerTree a -> [a] -> FingerTree a -> FingerTree a --  :         concatWithMiddle Empty [] right = right concatWithMiddle Empty (x:xs) right = x <| concatWithMiddle Empty xs right concatWithMiddle (Single y) xs right = y <| concatWithMiddle Empty xs right concatWithMiddle left [] Empty = left concatWithMiddle left xs Empty = concatWithMiddle left (init xs) Empty |> last xs concatWithMiddle left xs (Single y) = concatWithMiddle left xs Empty |> y --  :    concatWithMiddle left mid right = Deep (prefix left) deeper' (suffix right) where --  concatWithMiddle   ,     deeper' = concatWithMiddle (deeper left) mid' (deeper right) --      ,      --      ,    concatWithMiddle. mid' = nodes $ (toList $ suffix left) ++ mid ++ (toList $ prefix right) --  ><    . (><) :: FingerTree a -> FingerTree a -> FingerTree a left >< right = concatWithMiddle left [] right 

We can test, just as before, by looking at how 2 exampleTree >< exampleTree :

 > putStrLn $ toList $ exampleTree >< exampleTree thisisnotatreethisisnotatree > putStrLn $ toList $ concatWithMiddle exampleTree " " exampleTree thisisnotatree thisisnotatree 

Although it is clear that this code is functioning (no matter how punny it sounds), it is not entirely clear what we won, and whether we even won in terms of guaranteed asymptotic execution time. If we look at the base case of concatWithMiddle , we still find a ton of attachments! Each time we recurse inside the layer, we add elements to the median list (from unused affixes). Is it possible to achieve O(m) after this in the base case?
Surprisingly enough, the answer is no. We can prove that the base case will still take O(1) amortized time. The magic here is in the use of nodes. As we showed, when the function of nodes was determined, nodes guarantee the output list of no more than half of the elements of the input list. Using this property, we can easily track that the maximum length of the average list can be any during the counting.
When the counting begins, we know that the length of the average list is zero, because we passed the function concatWithMiddle an empty list in our definition >< . At each step, we add 2 affixes (suffix and prefix) to the middle list before adding nodes to it. We know that affixes have no more than 4 elements, which means that for the first iteration we will add no more than 8 elements, the output length after the function of nodes will be close to 8, but no more than 8. Indeed, if we start with a list less than or equal to 8 elements, then the length is divided in half, at the output we get again 8 or less elements. You can look at the example when we start with an empty middle list, and we will add 8 elements per step.
Step 0. The middle list is empty, 0 items
Step 1: Add 8 elements (4 from suffix, 4 from prefix). The function of nodes reduces the length by half, so the final list has 4 elements
Step 2: Add 8 elements. A total of 12, the nodes shorten the length to 6
Step 3: Add 8 elements. A total of 14, the nodes reduce the length to 7
Step 4: Add 8 elements. Only 15 knots shorten the length to 7
Note that the last 2 steps both had a list of the same size - once the calculations reach the limit - the average list reaches length 7, which is O(1) (constant), as a result we can confidently say that the base case occupies O(1) amortized execution time, since there will be no more than 8 connections.
Since the base case will consume constant time, the main one who invests time in the execution of our >< function, is recursion. Each recursive step, when we look into the deep trees of both the right and left trees of the concatWithMiddle function concatWithMiddle , we proceed to the base case immediately when at least one of the trees does not contain a Deeper constructor. The depth of these trees grows logarithmically with the growth of elements in it, if the finger tree consists of n elements, then its depth will be O(lg n) . And the runtime is proportional to the minimum depth of both trees, our asymptotic time limit is O(min(lg n,lg m))=O(lg(min(m,n))) , where n and m
- the number of elements in the right and left tree, respectively.
')
Well, in this part of the article we learned how to easily work with finger trees as with sequences.
However, the potential of finger trees is not exhausted. In the final part of the article, we will consider the additional possibilities of finger trees.