search

cs3110 / textbook

The CS 3110 Textbook, "OCaml Programming: Correct + Efficient + Beautiful"
Other
720 stars 132 forks source link

Persistent arrays are not covered #181

Open clarksmr opened 5 months ago

clarksmr commented 5 months ago

A new section in Chapter 8 should be added about persistent arrays, which are now covered in lecture.

ethanuppal commented 5 months ago

It would go here, after Red-Black Trees?

ethanuppal commented 5 months ago

I was wondering during class if in order for amortized $\mathcal{O}(1)$ cost per read operation there needs to be habitual copying of the array when version tree paths get "too long" or duplicate updates are performed? Or does rebasing handle that already (because it doesn't seem to resolve the issue that update paths can grow long)?