stm-tlist-0.1.1: Mutable, singly-linked list in STM

PortabilityRequires STM
Safe HaskellSafe-Infered




This module uses many names from Prelude, so consider importing it qualified:

import Data.STM.TList (TList)
import qualified Data.STM.TList as TList


The TList type

type TList a = TVar (TCell a)Source

A TList is a mutable linked list node. A TList node containing TNil is usually called a "hole" or "write end", and can be "filled" using append.

data TCell a Source


TCons a !(TList a) 



empty :: STM (TList a)Source

O(1). Construct a new, empty TList.

emptyIO :: IO (TList a)Source

O(1). IO variant of empty. See newTVarIO for the rationale.

cons :: a -> TList a -> STM (TList a)Source

O(1). Prepend an item to the list, returning the new beginning of the list.

append :: TList a -> a -> STM (TList a)Source

O(1). Append an item to the list, returning the new write end.

The TList normally points to a TNil, a "hole" into which the next item will be written. However, if it doesn't, append will silently overwrite the next item. It is up to the application to ensure that the TList points to a TNil, or that overwriting an item in this case is desirable.

appendList :: TList a -> [a] -> STM (TList a)Source

O(n). Append a list of items, returning the new write end.

fromList :: [a] -> STM (TList a, TList a)Source

O(n). Convert a pure list to a TList, returning the head (read end) and tail (write end) of the list.


These functions traverse the list strictly. They examine the list as it is now; they do not retry when the end of the list is reached.



:: STM b

What to do if the list is empty

-> (a -> TList a -> STM b)

What to do with the item and the remainder of the list

-> TList a

List node to examine

-> STM b 

O(1). Get the next item of the list (if available). Handle TNil (no items available) or TCons (next item) using the appropriate continuation.

The TList argument being at the end means uncons can be partially applied in many situations.

null :: TList a -> STM BoolSource

O(1). Return True if the list is empty.

drop :: Int -> TList a -> STM (TList a)Source

O(n). Skip the given number of items. Return the end of the list if a TNil is reached.

end :: TList a -> STM (TList a)Source

O(n). Traverse the list, stopping when a TNil is reached.

Bear in mind that TLists are mutable. In particular, the end of a TList is not as boring as the end of a pure list ([], a.k.a. "nil"). It is usually the write end, to which additional items may be appended.

length :: TList a -> STM IntSource

O(n). Traverse the list, returning its length.

foldl' :: (a -> b -> a) -> a -> TList b -> STM aSource

O(n). Traverse the list with an accumulator function and initial value.

toList :: TList a -> STM [a]Source

O(n). Traverse a TList, returning its items as a pure list.