Hi Simon,
I went to Aleksandar Prokopec's talk about Concurrent Tries at the Scala day earlier this week. I thought it was pretty cool. Here's the paper.
http://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf
Nice :)
Maybe we should have a Haskell version? Maybe we already do?
I think we do not have any nontrivial concurrent structures (we have MVar and FIFO + Semaphore built on top of it). Most of work seem to be done on persistent structures. On that front, Johan's unordered-containers package implements the hash tries, which are roughly the described CTries without concurrent updates. I am not sure it would be worth implementing a structure in Haskell that is inherently concurrent. For me it was always enough to wrap a persistent structure in an MVar, so updates are performed sequentially and accesses can be made in parallel. Such a structure would probably have to be strict and in an ST monad, to get a usable and deterministic behaviour. Any thoughts? Cheers, Milan