Data.STM.TList

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)

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

Constructors

TNil

TCons a !(TList a)

Instances

Typeable1 TCell

Construction

empty :: STM (TList a)

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

emptyIO :: IO (TList a)

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

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

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

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

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)

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

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

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

Traversal

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.

uncons

Arguments

:: 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 Bool

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

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

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)

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 Int

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

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

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

toList :: TList a -> STM [a]

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