Following on the previous post, I finally worked something out. Here's what's in the IHaskell notebook.

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).

module LFQ
( lfqCreate
 ,lfqPrint
 ,lfqEnqueue
 ,lfqDequeue) where

This notebook qualifies the STM package to help me remember what functions and types are included in the package.

import qualified Control.Concurrent.STM as STM

A queue is implemented as a transaction-wrapped list.

type LFQueue a = STM.TVar [a]

It seemed more useful to keep the queue in the IO pipeline, so all the functions return an IO (LFQueue a). The newLFQ function ensures that a new LFQueue is returned from the newTVarIO.

newLFQ :: [a] -> IO (LFQueue a)
newLFQ = STM.newTVarIO

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

lfqEnqueue :: a -> LFQueue a -> IO (LFQueue a)
lfqEnqueue x q = do
  queue <- readTVarIO q
  atomically $ writeTVar q (queue ++ [x])
  return q

Dequeueing from the queue returns the head of the queue and the updated queue.

lfqDequeue :: LFQueue a -> IO (a, LFQueue a)
lfqDequeue q = do
  queue <- readTVarIO q
  atomically $ writeTVar q (tail queue)
  return (head queue, q)

It's useful to be able to see the contents of the queue. lfqPrint is designed for composition, while lfqDisplay can be used as a standalone function.

lfqPrint :: Show a => LFQueue a -> IO ()
lfqPrint q = do
  queue <- readTVarIO q
  print queue

lfqDisplay :: (Show a) => IO (LFQueue a) -> IO ()
lfqDisplay q = q >>= lfqPrint

Here's some examples playing around with these functions:

ghci> lfqDisplay $ newLFQ [1,2,3] >>=
                   lfqEnqueue 5   >>=
                   lfqDequeue     >>=
                   (λ(_, q) -> return q)
[2,3,5]
ghci> lfqDisplay $ newLFQ [1,2,3]        >>=
                   lfqDequeue            >>=
                   (λ(_, q) -> return q) >>=
                   lfqEnqueue 5
[2,3,5]

I think this is a valid implementation of a lock-free queue, but I'm not entirely sure.

Here's the IHaskell notebook.