Alan Manuel Gloria <xxxxxx@gmail.com> writes:

> Thanks! My understanding of functional immutable sequence structures
> led me to think that all such would be O(log n) for an indexing
> operation. I'm thus quite curious on O(1) indexing on an immutable
> text.

As far as I understood:

Long story short, the text is cut into fixed-width substrings, say of
length 80, so text-ref is implemented principally like:

     (define (text-ref text idx)
       (let-values (((part-idx idx-within-part) (floor/ idx 80)))
         (let ((part (vector-ref (%text-parts part-idx) part-idx)))
           (string-ref part idx-within-part))))

Thus O(n) becomes O(1).

Taylan