Mergeable persistent data structures

Irmin is an OCaml library to design purely functional data structures that can be persisted on disk and be merged and synchronized efficiently. In this paper, we focus on the merge aspect of the library and present two data structures built on top of Irmin: (i) queues and (ii) ropes that extend
the corresponding purely functional data structures with a 3-way merge operation. We provide early theoretical and practical complexity results for these new data structures. Irmin is available as open-source code as part of the MirageOS project.

Benjamin Farinier, Thomas Gazagnaire and Anil Madhavapeddy. Journées Francophones des Langages Applicatifs. January 2015.