Hi,
I need a container data structure for storing anonymous objects - most likely things that have not value such as STM (), but probably other things as well. This will allow me to later on, iterate over the container and process those objects. Additionally I have the requirement that I need to be able to remove individual objects from this container. It needs to be linear time.
main = do
container <- nil
key1 <- cons 1 container
key2 <- cons 2 container
key3 <- cons 3 container
key4 <- cons 4 container
key5 <- cons 5 container
unlink key3 container
unlink key2 container
unlink key4 container
list <- toList container
putStrLn (show list)
The above should give: [1, 5]
What should I use?
Well, there are two ways, depending on what you want: the easy way and the hard way. If you can rethink your architecture to want the easy way, your life will be much nicer (but sometimes that's just not possible, I know). I am also going to buckle and give you an IO-ridden solution, because you are asking so specifically for that. With more context about your problem we may be able to give you advice about how to solve it more purely.
The easy way is a homogeneous container. That is, you have an interface like:
cons :: a -> Container a -> IO Key
unlink :: Key -> Container a -> IO ()
toList :: Container a -> IO [a]
This is no problem. A suitable type might be:
import Control.Concurrent.STM -- can do it with MVars, too, I just love STM
import qualified Data.Map as Map
newtype Key = Key Integer
data Container a = Container (TVar Integer) (TVar (Map.Map Integer a))
Where the Integer is a unique ID counter that gets incremented and stored in a key on every cons. Implementations left as an exercise for the reader (not to say we won't offer additional help).
The hard way is a heteroeneous container, with an interface like:
cons :: a -> Container -> IO (Key a)
unlink :: Key a -> Container -> IO ()
toList :: ???
I.e. each key can be associated with a different type of value. I don't know if there is an implementation of this on Hackage. Things like this might involve unsafeCoerce (though I guess you could do it without that by storing a set of IORefs or something). And the main thing is toList? What type should it return? Yeah a list, but a list of whats?
So I hope you want the easy way.
Maybe you'd like to give more details about the problem you're solving; i.e. not just what you want the code to look like, but actually what you're trying to accomplish, so we can help you get your mind out of the IO gutter.
Luke