Home | Notifications | New Note | Local | Federated | Search | Logout

Note Detail

dave@dthompson@toot.cat (2026-07-18 01:26:05)
one good choice that rhombus made is the use of relaxed radix trees for its list data type. I'm working on this for guile as a persistent vector type. it's interesting how implementing this differs from hash array mapped tries which are also based on radix trees. a good hash function creates hash codes that span the entire key range, but vector indices are sequential from 0 to n. this makes vector trees "leftwise dense" (all the values are packed into the left branches) whereas hash trees have stuff scattered all around. efficient traversal/modification of each structure looks quite different.