Data.Columbia.CycleDetection

These strategies are for cycle detection and construction of fixed points. Cycle detection is used wherever there are cycles in the reference graph implied by a Columbia file, or equivalently, if the file contains indefinitely large data. It ensures that reading and writing operations terminate in the presence of such data. The reconstruction of such data in a reading operation, implies that fixed points will be constructed. That way, while the reading operation terminates, it does construct indefinitely large (non-terminating) data, i.e. it reconstructs the indefinitely large data that was written.

The construction of cycles in the stream representation, is coordinated with the help of types that have non-trivial KeyComparable instances. These types furnish a comparison function, that can be used to compare data structure nodes, and thus detect cycles. These cycles are reflected as reference cycles in a Columbia file. Data at such types, where found in a cycle can be called "loop-breakers." If the data have cycles without loop breakers, the writing process will in fact not terminate, as there is no referentially transparent way (within Haskell) to detect the cycle.

Documentation

class Monad m => StateM m where

Minimal complete definition

mfy'

Associated Types

type StateOf m :: *

Methods

mfy' :: (StateOf m -> (StateOf m, a)) -> m a

Instances

Monad m => StateM (StateT s m)

Associated Types

type StateOf (StateT s m :: * -> *) :: *

Methods

mfy' :: (StateOf (StateT s m) -> (StateOf (StateT s m), a)) -> StateT s m a

StateM (ReaderT * (IORef s) IO)

Associated Types

type StateOf (ReaderT * (IORef s) IO :: * -> *) :: *

Methods

mfy' :: (StateOf (ReaderT * (IORef s) IO) -> (StateOf (ReaderT * (IORef s) IO), a)) -> ReaderT * (IORef s) IO a

get' :: StateM m => m (StateOf m)

put' :: StateM m => StateOf m -> m ()

type CycleDetectionR m = StateT (Map Word32 Dynamic) m

type CycleDetectionW m = StateT (Map (DynamicWithCtx KeyComparable) Word32) m

type CycleDetectionRIO = ReaderT (IORef (Map Word32 Dynamic)) IO

type CycleDetectionWIO = ReaderT (IORef (Map (DynamicWithCtx KeyComparable) Word32)) IO

cycleDetect :: forall ctx m t. (MonadFix m, StateM m, StateOf m ~ Map Pointer Dynamic, HasField ctx RWCtx, Data ctx t) => PolyTraversal ctx m t

cycleDetectW :: forall ctx m t. (StateM m, StateOf m ~ Map (DynamicWithCtx KeyComparable) Pointer, HasField ctx RWCtx, HasField ctx KeyCtx, Data ctx t) => PolyTraversalW ctx m t

runCycleDetectionR :: Monad m => ReaderT (SeekableStream (CycleDetectionR m) Word8) (CycleDetectionR m) t -> ReaderT (SeekableStream m Word8) m t

runCycleDetectionW :: Monad m => ReaderT (SeekableWriter (CycleDetectionW m) Word8) (CycleDetectionW m) t -> ReaderT (SeekableWriter m Word8) m t

data Pair k v

A Pair is a good data structures for associating a key and a value.

Constructors

Pair k v

Instances

(Sat (ctx (Pair k v)), Data ctx k, Data ctx v) => Data ctx (Pair k v)

Methods

gfoldl :: Proxy ctx -> (forall b c. Data ctx b => w (b -> c) -> b -> w c) -> (forall g. g -> w g) -> Pair k v -> w (Pair k v)

gunfold :: Proxy ctx -> (forall b r. Data ctx b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Pair k v)

toConstr :: Proxy ctx -> Pair k v -> Constr

dataTypeOf :: Proxy ctx -> Pair k v -> DataType

dataCast1 :: Typeable1 t => Proxy ctx -> (forall b. Data ctx b => w (t b)) -> Maybe (w (Pair k v))

dataCast2 :: Typeable2 t => Proxy ctx -> (forall b c. (Data ctx b, Data ctx c) => w (t b c)) -> Maybe (w (Pair k v))

ToRep (Pair k)

Methods

rep :: Pair k x -> Rep (Pair k) x

fun :: Pair k x -> Ann (Fix (Pair k))

val :: Pair k x -> Ann x

unrep :: Ann (Fix (Pair k)) -> Ann x -> Rep (Pair k) x -> Pair k x

(Eq v, Eq k) => Eq (Pair k v)

Methods

(==) :: Pair k v -> Pair k v -> Bool

(/=) :: Pair k v -> Pair k v -> Bool

(Ord v, Ord k) => Ord (Pair k v)

Methods

compare :: Pair k v -> Pair k v -> Ordering

(<) :: Pair k v -> Pair k v -> Bool

(<=) :: Pair k v -> Pair k v -> Bool

(>) :: Pair k v -> Pair k v -> Bool

(>=) :: Pair k v -> Pair k v -> Bool

max :: Pair k v -> Pair k v -> Pair k v

min :: Pair k v -> Pair k v -> Pair k v

(Read v, Read k) => Read (Pair k v)

Methods

readsPrec :: Int -> ReadS (Pair k v)

readList :: ReadS [Pair k v]

readPrec :: ReadPrec (Pair k v)

readListPrec :: ReadPrec [Pair k v]

(Show v, Show k) => Show (Pair k v)

Methods

showsPrec :: Int -> Pair k v -> ShowS

show :: Pair k v -> String

showList :: [Pair k v] -> ShowS

Ord k => KeyComparable (Pair k v)

Methods

isKeyed :: Pair k v -> Bool

keyCompare :: Pair k v -> Pair k v -> Ordering

(Typeable * k, Typeable * v) => RW (Pair k v)

Methods

readData :: Monad m => ReaderT * (SeekableStream m Word8) m (Pair k v)

writeData :: Monad m => Pair k v -> ReaderT * (SeekableWriter m Word8) m ()

type Rep (Pair k) v

type Rep (Pair k) v = Pair k v

pairCtor :: Constr

pairDataType :: DataType

Orphan instances

KeyComparable Bool

Methods

isKeyed :: Bool -> Bool

keyCompare :: Bool -> Bool -> Ordering

KeyComparable Char

Methods

isKeyed :: Char -> Bool

keyCompare :: Char -> Char -> Ordering

KeyComparable Float

Methods

isKeyed :: Float -> Bool

keyCompare :: Float -> Float -> Ordering

KeyComparable Int

Methods

isKeyed :: Int -> Bool

keyCompare :: Int -> Int -> Ordering

KeyComparable Int8

Methods

isKeyed :: Int8 -> Bool

keyCompare :: Int8 -> Int8 -> Ordering

KeyComparable Int16

Methods

isKeyed :: Int16 -> Bool

keyCompare :: Int16 -> Int16 -> Ordering

KeyComparable Int32

Methods

isKeyed :: Int32 -> Bool

keyCompare :: Int32 -> Int32 -> Ordering

KeyComparable Int64

Methods

isKeyed :: Int64 -> Bool

keyCompare :: Int64 -> Int64 -> Ordering

KeyComparable Ordering

Methods

isKeyed :: Ordering -> Bool

keyCompare :: Ordering -> Ordering -> Ordering

KeyComparable Word

Methods

isKeyed :: Word -> Bool

keyCompare :: Word -> Word -> Ordering

KeyComparable Word8

Methods

isKeyed :: Word8 -> Bool

keyCompare :: Word8 -> Word8 -> Ordering

KeyComparable Word16

Methods

isKeyed :: Word16 -> Bool

keyCompare :: Word16 -> Word16 -> Ordering

KeyComparable Word32

Methods

isKeyed :: Word32 -> Bool

keyCompare :: Word32 -> Word32 -> Ordering

KeyComparable Word64

Methods

isKeyed :: Word64 -> Bool

keyCompare :: Word64 -> Word64 -> Ordering

KeyComparable ()

Methods

isKeyed :: () -> Bool

keyCompare :: () -> () -> Ordering

Eq (DynamicWithCtx Eq)

Methods

(==) :: DynamicWithCtx Eq -> DynamicWithCtx Eq -> Bool

(/=) :: DynamicWithCtx Eq -> DynamicWithCtx Eq -> Bool

Eq (DynamicWithCtx KeyComparable)

Methods

(==) :: DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable -> Bool

(/=) :: DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable -> Bool

Ord (DynamicWithCtx KeyComparable)

Methods

compare :: DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable -> Ordering

(<) :: DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable -> Bool

(<=) :: DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable -> Bool

(>) :: DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable -> Bool

(>=) :: DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable -> Bool

max :: DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable

min :: DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable

KeyComparable t => Sat (KeyCtx t)

Methods

dict :: KeyCtx t

KeyComparable [t]

Methods

isKeyed :: [t] -> Bool

keyCompare :: [t] -> [t] -> Ordering

KeyComparable (Maybe t)

Methods

isKeyed :: Maybe t -> Bool

keyCompare :: Maybe t -> Maybe t -> Ordering

KeyComparable (Tree t)

Methods

isKeyed :: Tree t -> Bool

keyCompare :: Tree t -> Tree t -> Ordering

KeyComparable (Id x)

Methods

isKeyed :: Id x -> Bool

keyCompare :: Id x -> Id x -> Ordering

KeyComparable (Fix f)

Methods

isKeyed :: Fix f -> Bool

keyCompare :: Fix f -> Fix f -> Ordering

KeyComparable (DynamicWithCtx KeyComparable)

Methods

isKeyed :: DynamicWithCtx KeyComparable -> Bool

keyCompare :: DynamicWithCtx KeyComparable -> DynamicWithCtx KeyComparable -> Ordering

KeyComparable (Either t t2)

Methods

isKeyed :: Either t t2 -> Bool

keyCompare :: Either t t2 -> Either t t2 -> Ordering

KeyComparable (t1, t2)

Methods

isKeyed :: (t1, t2) -> Bool

keyCompare :: (t1, t2) -> (t1, t2) -> Ordering

KeyComparable (UArray i e)

Methods

isKeyed :: UArray i e -> Bool

keyCompare :: UArray i e -> UArray i e -> Ordering

KeyComparable (Array i e)

Methods

isKeyed :: Array i e -> Bool

keyCompare :: Array i e -> Array i e -> Ordering

KeyComparable (Map k v)

Methods

isKeyed :: Map k v -> Bool

keyCompare :: Map k v -> Map k v -> Ordering

KeyComparable (Const x x2)

Methods

isKeyed :: Const x x2 -> Bool

keyCompare :: Const x x2 -> Const x x2 -> Ordering

KeyComparable (t1, t2, t3)

Methods

isKeyed :: (t1, t2, t3) -> Bool

keyCompare :: (t1, t2, t3) -> (t1, t2, t3) -> Ordering

KeyComparable ((:+:) f g x)

Methods

isKeyed :: (f :+: g) x -> Bool

keyCompare :: (f :+: g) x -> (f :+: g) x -> Ordering

KeyComparable ((:*:) f g x)

Methods

isKeyed :: (f :*: g) x -> Bool

keyCompare :: (f :*: g) x -> (f :*: g) x -> Ordering

KeyComparable ((:@:) f g x)

Methods

isKeyed :: (f :@: g) x -> Bool

keyCompare :: (f :@: g) x -> (f :@: g) x -> Ordering

KeyComparable (t1, t2, t3, t4)

Methods

isKeyed :: (t1, t2, t3, t4) -> Bool

keyCompare :: (t1, t2, t3, t4) -> (t1, t2, t3, t4) -> Ordering

KeyComparable (t1, t2, t3, t4, t5)

Methods

isKeyed :: (t1, t2, t3, t4, t5) -> Bool

keyCompare :: (t1, t2, t3, t4, t5) -> (t1, t2, t3, t4, t5) -> Ordering