It's late and I really need to go to bed, but this is stuck in my head, so I played around with the stm package in an IHaskell notebook. Warning: This is a remarkably primitive attempt.

Lock-free queues

This is an experiment in playing with lock-free queues. It uses Haskell's STM package (e.g. via cabal install stm).

import Control.Concurrent
import Control.Concurrent.STM

A queue is implemented on top of a list.

data LFQueue a = LFQueue (TVar [a])

Enqueueing a value into an LFQueue transactionally appends the value v to the queue.

lfqEnqueue :: LFQueue a -> a -> STM ()
lfqEnqueue (LFQueue q) v = do
  queue <- readTVar q
  writeTVar q (queue ++ [v])

Similarly, dequeueing a value reads the current queue value, stores the tail of the inner list, and returns the head of the list.

lfqDequeue :: LFQueue a -> STM a
lfqDequeue (LFQueue q) = do
  queue <- readTVar q
  writeTVar q (tail queue)
  return $ head queue

Creating a new queue requires that the list be put into a new STM transaction, which is then wrapped inside the LFQueue.

lfqCreate :: [a] -> STM (LFQueue a)
lfqCreate x = do
  queue <- newTVar []
  writeTVar queue x
  return $ LFQueue queue

Here is where my Haskell skills shine. I'm stuck on where to go next.

• IHaskell notebook file
• Literate Haskell version