2008/12/28 John Ky

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

Hi John Sorry, I don't think I really grasp your problem? I think you're mixing two things: a) which data type to use to store whatever you like? * http://haskell.org/haskellwiki/Existential_type * Typable and Data.Dynamic etc.. b) Which container to use to put in stuff, return an identifier so that it can be removed by id again? There are many ways. Probably something like Data.Map or finger trees will do very well.. (use Int as key type and use max + 1 when inserting a new one or such?) I hope I've helped you in some way.. Sincerly Marc Weber