> Another nice thing about skip lists is that they are relatively easy to make into cheap persistent structures (aka functional structures), that is, structures

> Another nice thing about skip lists is that they are relatively easy to make into cheap persistent structures (aka functional structures), that is, structures where operations return a new immutable copy of the structure, but share most of the substructure with the previous version. The simplest purely functional balanced dictionary structures I am aware of are 2-3 trees, which are actually another way of viewing 1-2 skip lists, a deterministic variant of skip lists! http://scholar.google.com/scholar?cluster=10746226114047023400 http://scholar.google.com/scholar?cluster=107462261140470234...