[Haskell-cafe] Transactional container for storing anonymous deletable objects

[Luke Palmer]

2008/12/28 John Ky <newhoggy at gmail.com>

> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081228/4df3c68e/attachment.htm