Functional

The (aux fds sbral) module

Skew Binary Random-Access Lists, aka SBRALs.

Posted on April 10, 2026 | 11 min | 2177 words | Massimo Nocentini

A walkthrough of the Scheme module (aux fds sbral), showing how skew binary random-access lists support persistent front operations in constant amortized time and indexed lookup and update in logarithmic time. [Read More]

Eﬃcient representations for triangular substitutions

A comparison in miniKanren

This paper studies efficient representations for triangular substitutions in miniKanren, showing how skew binary random-access lists reduce lookup costs while preserving the advantages of a purely functional Scheme implementation. [Read More]

kanren sbral substitutions unification logic scheme functional lookup triangular minikanren

Purely functional random-access lists

Posted on October 1, 1995 | 1 min | 112 words | Chris Okasaki

Okasaki introduces purely functional random-access lists, a data structure that combines constant-time list operations with logarithmic lookup and update, offering an efficient persistent alternative to arrays in functional programs. [Read More]

randomaccess functional lists lookup update indexing arrays persistent logarithmic