<p>Functional data structures, or immutable data structures, are often achieved by copying old data to new data upon operation. Naively, it looks much less efficient than their imperical counterpart. However, there are techniques for efficiency (nb. immutable ones cannot be more efficient than imperical ones).</p>
<p>One technique, for example, is to implement a functional seqeunce with balanced tree. Then, on updating an entry of a functional sequence, only <span class="math-container">$O(log(n))$</span> entries need to be copied.</p>
<p>Another technique, which seems to be the main selling point of Chris Okasaki's sork, is to use laziness. Detailed in his book [1], however, I find it hard to understand as I'm not familiar with either ML or Haskell. Hence I'd like to try my luck here and <strong>see if anyone can explain how laziness helps implementing efficient immutable data structures</strong>. An example with a basic structure like (functional) sequence would suffice.</p>
<h3>Reference</h3>
<ul>
<li>[1] Purely Functional Data Structures-[Chris Okasaki]</li>
<li>[2] (related) <a href="https://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki">What&#39;s new in purely functional data structures since Okasaki?</a></li>
</ul>

CC BY-SA 4.0
2022-10-29T12:29:10.217Z
Consider $(\lambda xyz.17)\ L\ M\ N$. In a call-by-value scheme, all arguments, $L, M, N$ are evaluated even though they
are not used -- wasteful. Laziness does not do this. Similarly, consider $(\lambda x. x+x+x+x)M$:  In lazy and call-by-value evaluation, M is evaluated exactly once.
Martin Berger
CC BY-SA 4.0
2022-10-29T12:29:51.720Z
This question would be more suitable for [cs.stackexchange.com/](https://cs.stackexchange.com/).
Martin Berger
<cc.complexity-theory><ds.data-structures><functional-programming>
How does laziness help functional data structure?
Student
# How does laziness help functional data structure?

(Asked by: username_0 on 2022-10-29)

Functional data structures, or immutable data structures, are often achieved by copying old data to new data upon operation. Naively, it looks much less efficient than their imperical counterpart. However, there are techniques for efficiency (nb. immutable ones cannot be more efficient than imperical ones).

One technique, for example, is to implement a functional seqeunce with balanced tree. Then, on updating an entry of a functional sequence, only $O(log(n))$ entries need to be copied.

Another technique, which seems to be the main selling point of Chris Okasaki's sork, is to use laziness. Detailed in his book [1], however, I find it hard to understand as I'm not familiar with either ML or Haskell. Hence I'd like to try my luck here and **see if anyone can explain how laziness helps implementing efficient immutable data structures**. An example with a basic structure like (functional) sequence would suffice.

### Reference

* [1] Purely Functional Data Structures-[Chris Okasaki]
* [2] (related) [What's new in purely functional data structures since Okasaki?](https://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki)

**Tags:** cc.complexity-theory, ds.data-structures, functional-programming

> **Comments:**
> **username_1**: Consider $(\lambda xyz.17)\ L\ M\ N$. In a call-by-value scheme, all arguments, $L, M, N$ are evaluated even though they are not used -- wasteful. Laziness does not do this. Similarly, consider $(\lambda x. x+x+x+x)M$:  In lazy and call-by-value evaluation, M is evaluated exactly once.  
> **username_1**: This question would be more suitable for [cs.stackexchange.com/](https://cs.stackexchange.com/).  

---

## 0 answers

