I&#39;ve been in a situation a lot lately where I need to keep a collection of values, and keep track of them by a persistent index.<br>IO and ST refs can do this, but for various reasons I can&#39;t/don&#39;t want to use them.<br>
<br>My first hacked up attempt is as follows:<br><br>data IndexedCollection a = IndexedCollection {<br>    nextKey            :: Int,<br>    availableKeys :: [Int],<br>    items                :: (IntMap Int a)<br>} deriving (Show)<br>
<br>emptyIndexedCollection :: IndexedCollection a<br>emptyIndexedCollection = IndexedCollection 0 [] empty<br><br>addItem :: a -&gt; IndexedCollection a -&gt; (Int, IndexedCollection a)<br>addItem a (IndexedCollection nextKey&#39; []     t) = (nextKey&#39;, IndexedCollection (nextKey&#39; + 1) [] (insert nextKey&#39; a t))<br>
addItem a (IndexedCollection nextKey&#39; (k:ks) t) = (k, IndexedCollection nextKey&#39; ks (insert k a t))<br><br>removeItem :: Int -&gt; IndexedCollection a -&gt; IndexedCollection a<br>removeItem k (IndexedCollection nextKey&#39; ks t) = IndexedCollection nextKey&#39; (k:ks) (delete k t)<br>
<br>lookupItem :: Int -&gt; IndexedCollection a -&gt; Maybe a<br>lookupItem k (IndexedCollection _ _ t) = lookup k t<br><br>Basically: when you add an item, use the first index in availableKeys
(if there is one), otherwise use &quot;nextKey&quot; for the index, and then
increment it for the next item. <br>
When and Item is removed, add it&#39;s index to availableKeys<br><br>This keeps the code for keeping track of/generating indexes hidden away from the rest of the program which is nice, and it remains fairly efficient.<br>
Items will be added and removed on very regular basis. Often enough that I&#39;m slightly concerned about overflow of nextKey for very long run times, and hence the availableKeys list.<br><br>Does anyone know of a better/already existent data structure for handling this problem?<br>
<br>Or perhaps a better way of keeping a &quot;key pool&quot; than my availableKeys solution?<br><br>- Job<br>