Efficient Implementation of Linearly Used Finite Maps?

Abstract. Typical functional implementations of finite maps are based on association lists or balanced binary trees. This paper describes a non-typical implementation using mutable references internally. The interface of the data structure is similar to the interface of the Data.Map module in Haskell. The main difference is that keys of maps can only be identifiers. Identifiers are members of an abstract data type. The implementation provides functions which helps the creation and dis-tribution of identifiers. If the number of used maps has an upper bound and the maps are used linearly, then the insert, delete and search operations are constant time operations independently of the number of keys. A number of pointer al-gorithms can be implemented with finite maps so that these constraints hold. These algorithms could also be implemented with mutable refer-ences, but the use of finite maps gives a more functional look and feel. Prototype implementation of the data structure with usage examples exists in Clean and Haskell. This paper describes the main points of the implementations and presents two usage examples: An algorithm which finds strongly connected components in directed graphs and a sequence data structure implementation.