Abstract
A numeration system enables large numbers to be represented efficiently by giving different weights to successive digits (e.g. 1, 10, 100, 1 000, etc.). This idea also inspires the design of remarkably efficient persistent structures, notably for direct-access lists and priority queues. We will then describe the use of non-regular algebraic types to implement such structures in a simpler and more typing-controlled way. We conclude with a studyof Hinze and Paterson's finger trees , a versatile structure that applies several of these techniques.
