<p>While you wind up with a large number of intermediate fingertree structures, they share the vast majority of their structure with one another. In the end you allocate at most twice as much memory as in the idealized case, and the remainder is freed with the first collection. The asymptotics of this are the same as good as they can get, since you need a fingertree filled with n values in the end.</p>

<p>You can build the fingertree by using <code>Data.FingerTree.replicate</code> and them using <code>FingerTree.fmapWithPos</code> to look up your values in an array which plays the role of your finite sequence, or using <code>traverseWithPos</code> to peel them out of a list or other known-sized container.</p>

<p>This will allocate $O(\log n)$ nodes for the initial replicated skeleton, and then replace them with the $O(n)$ nodes needed to populate the skeleton, 'wasting' at most $O(\log n)$ memory until garbage collection cleans things up, So instead of the optimal ~1000 nodes you'd have to pay for ~1010, instead of ~2000 from cons'd construction.</p>

<p>Finally, you can avoid using replicate at and generating that interim $O(\log n)$ memory replicated tree, by using <code>replicateA</code>, but as @sclv noted, the tupling for manipulating the state intrinsic to <code>mapAccumL</code> or traversing with a state monad yourself will actually introduce proportionally similar overhead to just paying for all the extra product cells.</p>

<p>TL;DR If I had to do this, I'd probably use:</p>

<pre><code>rep :: (Int -&gt; a) -&gt; Int -&gt; Seq a 
rep f n = mapWithIndex (const . f) $ replicate n () 
</code></pre>

<p>and to index into a fixed sized array I'd just supply <code>(arr !)</code> for <code>f</code> above.</p>

CC BY-SA 3.0
2011-03-11T20:16:09.127Z
2016-02-20T05:54:39.323Z
2016-02-20T05:54:39.323Z
Edward Kmett
<p>Riffing on jbapple's excellent answer regarding <code>replicate</code>, but using <code>replicateA</code> (which <code>replicate</code> is built on) instead, I came up with the following:</p>

<pre><code>--Unlike fromList, one needs the length explicitly. 
myFromList :: Int -&gt; [b] -&gt; Seq b
myFromList l xs = flip evalState xs $ Seq.replicateA l go
    where go = do
           (y:ys) &lt;- get
            put ys
            return y
</code></pre>

<p><code>myFromList</code> (in a slightly more efficient version) is already <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/containers-0.4.0.0/src/Data-Sequence.html#fromList2">defined and used internally</a> in <code>Data.Sequence</code> for constructing finger trees that are results of sorts.</p>

<p>In general, the intuition for <code>replicateA</code> is simple. <code>replicateA</code> is built on top of the <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/containers-0.4.0.0/src/Data-Sequence.html#applicativeTree">applicativeTree</a> function. <code>applicativeTree</code> takes a <em>piece</em> of a tree of a size <code>m</code>, and produces a well-balanced tree containing <code>n</code> copies of this. The cases for <code>n</code> up to 8 (a single <code>Deep</code> finger) are hard coded. Anything above this, and it invokes itself recursively. The "applicative" element is simply that it interleaves the construction of the tree with threading effects through, such as, in the case of the above code, state.</p>

<p>The <code>go</code> function, which is replicated, is simply an action which gets the current state, pops an element off the top, and replaces the remainder. On each invocation, it thus steps further down the list provided as input.</p>

<p><strong>Some more concrete notes</strong></p>

<pre><code>main = print (length (show (Seq.fromList [1..10000000::Int])))
</code></pre>

<p>On some simple tests, this yielded an  interesting performance tradeoff. The main function above ran almost 1/3 lower with myFromList than with <code>fromList</code>. On the other hand, <code>myFromList</code> used a constant heap of 2MB, while the standard <code>fromList</code> used up to 926MB. That 926MB arises from needing to hold the entire list in memory at once. Meanwhile, the solution with <code>myFromList</code> is able to consume the structure in a lazy streaming fashion. The issue with speed results from the fact that <code>myFromList</code> must perform roughly twice as many allocations (as a result of the pair construction/destruction of the state monad) as <code>fromList</code>. We can eliminate those allocations by moving to a CPS-transformed state monad, but that results in holding on to far more memory at any given time, because the loss of laziness requires traversing the list in a non-streaming manner.</p>

<p>On the other hand, if rather than forcing the entire sequence with a show, I move to just extracting the head or last element, <code>myFromList</code> immediately presents a bigger win -- extracting the head element is nearly instant, and extracting the last element is 0.8s. Meanwhile, with the standard <code>fromList</code>, extracting either the head or last element costs ~2.3 seconds.</p>

<p>This is all details, and is a consequence of purity and laziness. In a situation with mutation and random access, I would imagine the <code>replicate</code> solution is strictly better.</p>

<p>However, it does raise the question of whether there is a way to rewrite <code>applicativeTree</code> such that <code>myFromList</code> is strictly more efficient. The issue is, I think, that the applicative actions are executed in a different order than the tree is naturally traversed, but I haven't fully worked through how this works, or if there is a way to resolve this.</p>

CC BY-SA 2.5
2011-03-10T19:31:15.753Z
(1) Interesting.  This looks like _the_ correct way to do this task.  I am surprised to hear that this is slower than `fromList` when the entire sequence is forced.  (2) Maybe this answer is too code-heavy and language-dependent for cstheory.stackexchange.com.  It would be great if you can add an explanation how `replicateA` works in a language-independent manner.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-10T18:17:09.157Z
2011-03-11T16:21:13.850Z
2011-03-11T16:21:13.850Z
sclv
<p>GHC's <a href="http://www.haskell.org/ghc/docs/latest/html/libraries/containers-0.4.0.0/src/Data-Sequence.html#replicate"><code>Data.Sequence</code>'s <code>replicate</code> function</a>
 builds a fingertree in $O(\lg n)$ time and space, but this is enabled by knowing the elements that go on the right spine of the finger tree from the get-go. This library was written by the authors of the original paper on 2-3 finger trees.</p>

<p>If you want to build a finger tree by repeated concatenation, you might be able to reduce the transient space usage while building by changing the representation of the spines. The spines on 2-3 finger trees are cleverly stored as synchronized singly-linked lists. If, instead, you store the spines as deques, it may be possible to save space when concatenating trees. The idea is that concatenating two trees of the same height takes $O(1)$ space by reusing the spines of the trees. When concatenating 2-3 finger trees as originally described, the spines that are internal to the new tree can no longer be used as-is.</p>

<p><a href="http://www.math.tau.ac.il/~haimk/papers/loglog23.ps">Kaplan and Tarjan's "Purely Functional Representations of Catenable Sorted Lists"</a> describes a more complicated finger tree structure. This paper (in section 4) also discusses a construction similar to deque suggestion I made above. I believe the structure they describe can concatenate two trees of equal height in $O(1)$ time and space. For building finger trees, is this enough space saving for you?</p>

<p>NB: Their use of the word "bootstrapping" means something a bit different than your use above. They mean storing part of a data structure using a simpler version of the same structure.</p>

CC BY-SA 2.5
2011-03-09T18:26:41.843Z
A very interesting idea.  I'll have to look into this and see what the trade-offs would be to the overall data structure.
jbondeson
CC BY-SA 2.5
2011-03-10T03:55:36.207Z
I meant for there to be two ideas in this answer: (1) The replicate idea (2) Faster concatenate for nearly-equally-sized trees. I think the replicate idea can build finger trees in very little extra space if the input is an array.
jbapple
CC BY-SA 2.5
2011-03-10T16:06:40.443Z
Yes, I saw both.  Sorry I didn't comment on both of them.  I'm looking into the replicate code first -- though I'm definitely stretching my Haskell knowledge as far as it will go.  At first blush it does look like it could solve most of the issues I'm having, provided you have fast random access.  The fast concat could be a little more generic solution in the case of no random access.
jbondeson
CC BY-SA 2.5
2011-03-09T07:52:09.070Z
2011-03-09T16:01:59.077Z
2011-03-09T16:01:59.077Z
jbapple
<p>After working with 2-3 finger trees for quite a bit I have been impressed by their speed in most operations.  However, the one issue I have run into is the large overhead associated with the initial creation of a large finger tree.  Because building is defined as a sequence of concatenation operations you end up building a large number of finger tree structures that are unneeded.  </p>

<p>Due to the complex nature of 2-3 finger trees I see no intuitive method for bootstrapping them, and all my searches have come up empty. So the question is, how could you go about bootstrapping a 2-3 finger tree with minimal overhead?</p>

<p>To be explicit: given a sequence $S$ of known length $n$ generate the finger tree representation of $S$ with minimal operations.</p>

<p>The naive way to accomplish is successive calls to the cons operation (in the literature the '$\triangleleft$' operator).  However, this will create $n$ distinct finger tree structures representing all the slices of $S$ for $[1..i]$.</p>

CC BY-SA 2.5
2011-03-08T16:57:30.537Z
Does [Finger trees: a simple general-purpose data structure](http://www.soi.city.ac.uk/~ross/papers/FingerTree.html) by Hinze and Paterson provide answers?
Dave Clarke
CC BY-SA 2.5
2011-03-08T17:06:22.353Z
@Dave I actually implemented off their paper, and they don't address efficient creation.
jbondeson
CC BY-SA 2.5
2011-03-08T17:07:16.937Z
I figured as much.
Dave Clarke
CC BY-SA 2.5
2011-03-09T05:10:19.957Z
Could you be a bit more specific on what you mean by "build" in this case? Is this an unfoldr?
jbapple
CC BY-SA 2.5
2011-03-09T18:07:10.393Z
@jbapple - I edited to be a more explicit, sorry for the confusion.
jbondeson
CC BY-SA 2.5
2011-03-10T03:51:39.470Z
@jbondeson - That is helpful. Does the input sequence support random access in O(1) time, like an array?
jbapple
<ds.data-structures><functional-programming>
Bootstrapping a Finger Tree Structure
jbondeson
# Bootstrapping a Finger Tree Structure

(Asked by: username_0 on 2011-03-08)

After working with 2-3 finger trees for quite a bit I have been impressed by their speed in most operations. However, the one issue I have run into is the large overhead associated with the initial creation of a large finger tree. Because building is defined as a sequence of concatenation operations you end up building a large number of finger tree structures that are unneeded.

Due to the complex nature of 2-3 finger trees I see no intuitive method for bootstrapping them, and all my searches have come up empty. So the question is, how could you go about bootstrapping a 2-3 finger tree with minimal overhead?

To be explicit: given a sequence $S$ of known length $n$ generate the finger tree representation of $S$ with minimal operations.

The naive way to accomplish is successive calls to the cons operation (in the literature the '$\triangleleft$' operator). However, this will create $n$ distinct finger tree structures representing all the slices of $S$ for $[1..i]$.

**Tags:** ds.data-structures, functional-programming

> **Comments:**
> **username_1**: Does [Finger trees: a simple general-purpose data structure](http://www.soi.city.ac.uk/~ross/papers/FingerTree.html) by Hinze and Paterson provide answers?  
> **username_0**: @Dave I actually implemented off their paper, and they don't address efficient creation.  
> **username_1**: I figured as much.  
> **username_2**: Could you be a bit more specific on what you mean by "build" in this case? Is this an unfoldr?  
> **username_0**: @username_2 - I edited to be a more explicit, sorry for the confusion.  
> **username_2**: @username_0 - That is helpful. Does the input sequence support random access in O(1) time, like an array?  

---

## 3 answers

### Answer by username_2 on 2011-03-09. Score: 16 | Accepted answer

GHC's [`Data.Sequence`'s `replicate` function](http://www.haskell.org/ghc/docs/latest/html/libraries/containers-0.4.0.0/src/Data-Sequence.html#replicate)
builds a fingertree in $O(\lg n)$ time and space, but this is enabled by knowing the elements that go on the right spine of the finger tree from the get-go. This library was written by the authors of the original paper on 2-3 finger trees.

If you want to build a finger tree by repeated concatenation, you might be able to reduce the transient space usage while building by changing the representation of the spines. The spines on 2-3 finger trees are cleverly stored as synchronized singly-linked lists. If, instead, you store the spines as deques, it may be possible to save space when concatenating trees. The idea is that concatenating two trees of the same height takes $O(1)$ space by reusing the spines of the trees. When concatenating 2-3 finger trees as originally described, the spines that are internal to the new tree can no longer be used as-is.

[Kaplan and Tarjan's "Purely Functional Representations of Catenable Sorted Lists"](http://www.math.tau.ac.il/~haimk/papers/loglog23.ps) describes a more complicated finger tree structure. This paper (in section 4) also discusses a construction similar to deque suggestion I made above. I believe the structure they describe can concatenate two trees of equal height in $O(1)$ time and space. For building finger trees, is this enough space saving for you?

NB: Their use of the word "bootstrapping" means something a bit different than your use above. They mean storing part of a data structure using a simpler version of the same structure.

> **Comments:**
> **username_0**: A very interesting idea.  I'll have to look into this and see what the trade-offs would be to the overall data structure.  
> **username_2**: I meant for there to be two ideas in this answer: (1) The replicate idea (2) Faster concatenate for nearly-equally-sized trees. I think the replicate idea can build finger trees in very little extra space if the input is an array.  
> **username_0**: Yes, I saw both.  Sorry I didn't comment on both of them.  I'm looking into the replicate code first -- though I'm definitely stretching my Haskell knowledge as far as it will go.  At first blush it does look like it could solve most of the issues I'm having, provided you have fast random access.  The fast concat could be a little more generic solution in the case of no random access.  

---

### Answer by username_4 on 2011-03-10. Score: 10

Riffing on username_2's excellent answer regarding replicate, but using replicateA (which replicate is built on) instead, I came up with the following:
--Unlike fromList, one needs the length explicitly. 
myFromList :: Int -> [b] -> Seq b
myFromList l xs = flip evalState xs $ Seq.replicateA l go
    where go = do
           (y:ys) <- get
            put ys
            return y

myFromList (in a slightly more efficient version) is already defined and used internally in Data.Sequence for constructing finger trees that are results of sorts.
In general, the intuition for replicateA is simple. replicateA is built on top of the applicativeTree function. applicativeTree takes a piece of a tree of a size m, and produces a well-balanced tree containing n copies of this. The cases for n up to 8 (a single Deep finger) are hard coded. Anything above this, and it invokes itself recursively. The "applicative" element is simply that it interleaves the construction of the tree with threading effects through, such as, in the case of the above code, state.
The go function, which is replicated, is simply an action which gets the current state, pops an element off the top, and replaces the remainder. On each invocation, it thus steps further down the list provided as input.
Some more concrete notes
main = print (length (show (Seq.fromList [1..10000000::Int])))

On some simple tests, this yielded an  interesting performance tradeoff. The main function above ran almost 1/3 lower with myFromList than with fromList. On the other hand, myFromList used a constant heap of 2MB, while the standard fromList used up to 926MB. That 926MB arises from needing to hold the entire list in memory at once. Meanwhile, the solution with myFromList is able to consume the structure in a lazy streaming fashion. The issue with speed results from the fact that myFromList must perform roughly twice as many allocations (as a result of the pair construction/destruction of the state monad) as fromList. We can eliminate those allocations by moving to a CPS-transformed state monad, but that results in holding on to far more memory at any given time, because the loss of laziness requires traversing the list in a non-streaming manner.
On the other hand, if rather than forcing the entire sequence with a show, I move to just extracting the head or last element, myFromList immediately presents a bigger win -- extracting the head element is nearly instant, and extracting the last element is 0.8s. Meanwhile, with the standard fromList, extracting either the head or last element costs ~2.3 seconds.
This is all details, and is a consequence of purity and laziness. In a situation with mutation and random access, I would imagine the replicate solution is strictly better.
However, it does raise the question of whether there is a way to rewrite applicativeTree such that myFromList is strictly more efficient. The issue is, I think, that the applicative actions are executed in a different order than the tree is naturally traversed, but I haven't fully worked through how this works, or if there is a way to resolve this.

> **Comments:**
> **username_5**: (1) Interesting.  This looks like _the_ correct way to do this task.  I am surprised to hear that this is slower than `fromList` when the entire sequence is forced.  (2) Maybe this answer is too code-heavy and language-dependent for cstheory.stackexchange.com.  It would be great if you can add an explanation how `replicateA` works in a language-independent manner.  

---

### Answer by username_3 on 2011-03-11. Score: 9

While you wind up with a large number of intermediate fingertree structures, they share the vast majority of their structure with one another. In the end you allocate at most twice as much memory as in the idealized case, and the remainder is freed with the first collection. The asymptotics of this are the same as good as they can get, since you need a fingertree filled with n values in the end.
You can build the fingertree by using Data.FingerTree.replicate and them using FingerTree.fmapWithPos to look up your values in an array which plays the role of your finite sequence, or using traverseWithPos to peel them out of a list or other known-sized container.
This will allocate $O(\log n)$ nodes for the initial replicated skeleton, and then replace them with the $O(n)$ nodes needed to populate the skeleton, 'wasting' at most $O(\log n)$ memory until garbage collection cleans things up, So instead of the optimal ~1000 nodes you'd have to pay for ~1010, instead of ~2000 from cons'd construction.
Finally, you can avoid using replicate at and generating that interim $O(\log n)$ memory replicated tree, by using replicateA, but as @username_4 noted, the tupling for manipulating the state intrinsic to mapAccumL or traversing with a state monad yourself will actually introduce proportionally similar overhead to just paying for all the extra product cells.
TL;DR If I had to do this, I'd probably use:
rep :: (Int -> a) -> Int -> Seq a 
rep f n = mapWithIndex (const . f) $ replicate n () 

and to index into a fixed sized array I'd just supply (arr !) for f above.


---

