Finger Trees: A Simple General-purpose Data Structure

March 2006Finger Trees: A Simple General-purpose Data StructureFinger Trees: A Simple General-purpose Data Structure

This paper introduces the data structure behind the Seq type.

The Data.Sequence module first appears in the base library in GHC 6.6, before being moved into a separate containers package in GHC 6.8. It is still in common use today.

Authors: Ralf Hinze and Ross Paterson