Purely Functional Random-Access Lists implemented in Scheme (Racket)

David Van Horn написал на Scheme (точнее, на Racket) чистый функциональный список с произвольным достпупом (исходники здесь).

Под капотом реализация из Okasaki (FPCA '95): список в виде дерева со всеми вытекющими.

Например:

$ (time (length (make-list (expt 2 100000) 'x)))
cpu time: 5659 real time: 5678 gc time: 1823
...
$ (define ls* (time (list-set ls 8989891824312123128989813 'q)))
cpu time: 1850 real time: 1864 gc time: 291

А если еще вспомнить Guy Steele (... foldl and foldr considered slightly harmful, pdf), то подобная реализация хорошо подходит для алгоритмов распараллеливания.