<p><strong>Contiguous arrays do not mix with lazy evaluation.</strong>  That's why Haskell doesn't have contiguous arrays as a primitive type, and why even GHC has a poor API for them. As such, I sought for a workaround.</p>
<p>One quirk about contiguous arrays is that, though they have O(1) access time, this complexity is an artifact emerging from the word length being finite. If there were no upper bound to the word length, the minimum time complexity of indexing would be logarithmic.</p>
<p>And indeed, even in Haskell, there exists a data structure with log-time indexing, namely the binary tree (<a href="https://codegolf.stackexchange.com/q/260693/89459">relevant CG SE post</a>):</p>
<pre><code>data LogList a = Leaf | Branch a (LogList a) (LogList a)

(!?) :: LogList a -&gt; Int -&gt; Maybe a
Leaf !? _ = Nothing
Branch x _ _ !? 1 = Just x
Branch _ xs ys !? n
  | n &lt;= 0 = Nothing
  | even n = xs !? quot n 2
  | otherwise = ys !? quot n 2
</code></pre>
<p>Note that it has log-time cons and uncons as well:</p>
<pre><code>cons :: a -&gt; LogList a -&gt; LogList a
cons x Leaf = Branch x Leaf Leaf
cons x (Branch y xs ys) = Branch x (cons y ys) xs

uncons :: LogList a -&gt; Maybe (a, LogList a)
uncons Leaf = Nothing
uncons (Branch x xs ys) = Just . (,) x $ case uncons xs of
    Nothing -&gt; Leaf
    Just (y, zs) -&gt; Branch y ys zs
</code></pre>
<p>And as for insertion and deletion at an arbitrary index, though I've not formally implemented them, I guess they'd take linear-logarithmic time.</p>
<p>Another big bonus is the existence of lazy infinite lists, for example:</p>
<pre><code>repeat :: a -&gt; LogList a
repeat x = Branch x (repeat x) (repeat x)
</code></pre>
<p>So why doesn't Haskell provide this data structure in the <code>base</code> package, nor even in the <code>containers</code> package? Is there any caveat I've not seen?</p>

<standard-library><haskell><data-structures><lazy-evaluation>
Is it practical to use binary trees as a sequential container?
CC BY-SA 4.0
2024-05-14T05:45:26.883Z
`Data.Sequence` in the `containers` package uses [finger trees](http://www.staff.city.ac.uk/~ross/papers/FingerTree.html).
alephalpha
CC BY-SA 4.0
2024-05-14T05:46:20.610Z
@alephalpha IIRC, `Data.Sequence` can only have finitely many items.
Dannyu NDos
CC BY-SA 4.0
2024-05-15T13:58:39.100Z
Minor typo: "continugous" for "contiguous".
chepner
CC BY-SA 4.0
2024-05-16T19:25:24.177Z
I think the main point in favour of using binary trees for immutable lists, is that they allow concatenation in O(1) time, or O(log n) time if you want to keep them balanced. So they might be worth considering over linked lists (aka cons lists) if concatenation is the primary way that lists are meant to be built in your language.
kaya3
<h1>Somewhat</h1>
<p>All of the points you've made stand, but here are the most obvious concerns, in a vague order of importance:</p>
<ul>
<li>O(n) space overhead, on top of the data you're storing</li>
<li>Pretty bad cache locality</li>
<li>Infinite datastructures aren't actually that useful most of the time (big bonus is a stretch at best, I think)</li>
<li>Something like a finger tree is really just better for almost everything except allowing infinite structure</li>
</ul>

CC BY-SA 4.0
2024-05-15T04:36:40.667Z
2024-05-15T04:48:15.757Z
2024-05-15T04:48:15.757Z
blueberry
CC BY-SA 4.0
2024-05-17T00:12:02.860Z
What is a "finger tree"?
Karl Knechtel
CC BY-SA 4.0
2024-05-17T03:54:03.507Z
@KarlKnechtel See alephalpha's comment above.
Dannyu NDos
# Is it practical to use binary trees as a sequential container?
Posted by: username_0 on 2024-05-14
Contiguous arrays do not mix with lazy evaluation.  That's why Haskell doesn't have contiguous arrays as a primitive type, and why even GHC has a poor API for them. As such, I sought for a workaround.
One quirk about contiguous arrays is that, though they have O(1) access time, this complexity is an artifact emerging from the word length being finite. If there were no upper bound to the word length, the minimum time complexity of indexing would be logarithmic.
And indeed, even in Haskell, there exists a data structure with log-time indexing, namely the binary tree (relevant CG SE post):
data LogList a = Leaf | Branch a (LogList a) (LogList a)

(!?) :: LogList a -> Int -> Maybe a
Leaf !? _ = Nothing
Branch x _ _ !? 1 = Just x
Branch _ xs ys !? n
  | n <= 0 = Nothing
  | even n = xs !? quot n 2
  | otherwise = ys !? quot n 2

Note that it has log-time cons and uncons as well:
cons :: a -> LogList a -> LogList a
cons x Leaf = Branch x Leaf Leaf
cons x (Branch y xs ys) = Branch x (cons y ys) xs

uncons :: LogList a -> Maybe (a, LogList a)
uncons Leaf = Nothing
uncons (Branch x xs ys) = Just . (,) x $ case uncons xs of
    Nothing -> Leaf
    Just (y, zs) -> Branch y ys zs

And as for insertion and deletion at an arbitrary index, though I've not formally implemented them, I guess they'd take linear-logarithmic time.
Another big bonus is the existence of lazy infinite lists, for example:
repeat :: a -> LogList a
repeat x = Branch x (repeat x) (repeat x)

So why doesn't Haskell provide this data structure in the base package, nor even in the containers package? Is there any caveat I've not seen?
**Tags:** standard-library haskell data-structures lazy-evaluation
> **Comments:**
> **username_1**: `Data.Sequence` in the `containers` package uses [finger trees](http://www.staff.city.ac.uk/~ross/papers/FingerTree.html).  
> **username_0**: @alephalpha IIRC, `Data.Sequence` can only have finitely many items.  
> **username_2**: Minor typo: "continugous" for "contiguous".  
> **username_3**: I think the main point in favour of using binary trees for immutable lists, is that they allow concatenation in O(1) time, or O(log n) time if you want to keep them balanced. So they might be worth considering over linked lists (aka cons lists) if concatenation is the primary way that lists are meant to be built in your language.  
---
## 1 answers
### Answer by username_4 on 2024-05-15. Score: 2
# Somewhat

All of the points you've made stand, but here are the most obvious concerns, in a vague order of importance:

* O(n) space overhead, on top of the data you're storing
* Pretty bad cache locality
* Infinite datastructures aren't actually that useful most of the time (big bonus is a stretch at best, I think)
* Something like a finger tree is really just better for almost everything except allowing infinite structure
> **Comments:**
> **username_5** (2024-05-17): What is a "finger tree"?  
> **username_0** (2024-05-17): @KarlKnechtel See alephalpha's comment above.  
---
