Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Delta

Contents

Synopsis
Delta encodings
Embedding of types and delta encodings
Internal

Synopsis

class Delta delta where
- type Base delta :: Type
- apply :: delta -> Base delta -> Base delta
data NoChange a = NoChange
newtype Replace a = Replace a
data DeltaList a = Append [a]
data DeltaSet1 a
- = Insert a
- | Delete a
data DeltaSet a
mkDeltaSet :: Ord a => Set a -> Set a -> DeltaSet a
deltaSetToList :: DeltaSet a -> [ DeltaSet1 a]
deltaSetFromList :: Ord a => [ DeltaSet1 a] -> DeltaSet a
data Embedding da db
class Semigroupoid (c :: k -> k -> Type ) where
- o :: forall (j :: k) (k1 :: k) (i :: k). c j k1 -> c i j -> c i k1
data Embedding' da db where
- Embedding' :: ( Delta da, Delta db, a ~ Base da, b ~ Base db) => {..} -> Embedding' da db
mkEmbedding :: Embedding' da db -> Embedding da db
fromEmbedding :: ( Delta da, Delta db) => Embedding da db -> Embedding' da db
pair :: Embedding da1 db1 -> Embedding da2 db2 -> Embedding (da1, da2) (db1, db2)
liftUpdates :: Delta da => Embedding da db -> [da] -> Base da -> ( Base db, [db])
replaceFromApply :: ( Delta da, a ~ Base da) => Embedding' da ( Replace a)
inject :: Embedding da db -> Base da -> Machine da db
project :: Embedding da db -> Base db -> Either SomeException ( Base da, Machine da db)
data Machine da db = Machine {
- state_ :: !( Base db)
- step_ :: ( Base da, da) -> (db, Machine da db)
}
idle :: Delta da => Base da -> Machine da da
pairMachine :: Machine da1 db1 -> Machine da2 db2 -> Machine (da1, da2) (db1, db2)
fromState :: Delta db => (( Base da, da) -> ( Base db, s) -> (db, s)) -> ( Base db, s) -> Machine da db

Synopsis

Delta encodings.

The type constraint Delta delta means that the type delta is a delta encoding of the corresponding base type Base delta .

Delta encodings can be transformed into each other using an Embedding .

Delta encodings

class Delta delta where Source #

Type class for delta encodings.

Associated Types

type Base delta :: Type Source #

Base type for which delta represents a delta encoding. This is implemented as a type family, so that we can have multiple delta encodings for the same base type.

FIXME: Better name for Base ? It's sooo generic. Pier, dock, ground, anchor, site, …

Methods

apply :: delta -> Base delta -> Base delta Source #

Apply a delta encoding to the base type.

Instances

Instances details

Delta delta => Delta [delta] Source #	A list of deltas can be applied like a single delta. This overloading of `apply` is very convenient. Order is important: The `head` of the list is applied last . This way, we have a morphism to the `Endo` `Monoid` : apply [] = id apply (d1 <> d2) = apply d1 . apply d2
Instance details Defined in Data.Delta Associated Types type Base [delta] Source # Methods apply :: [delta] -> Base [delta] -> Base [delta] Source #
Delta delta => Delta ( Maybe delta) Source #	A delta can be optionally applied.
Instance details Defined in Data.Delta Associated Types type Base ( Maybe delta) Source # Methods apply :: Maybe delta -> Base ( Maybe delta) -> Base ( Maybe delta) Source #
Delta delta => Delta ( NonEmpty delta) Source #	For convenience, a nonempty list of deltas can be applied like a list of deltas.
Instance details Defined in Data.Delta Associated Types type Base ( NonEmpty delta) Source # Methods apply :: NonEmpty delta -> Base ( NonEmpty delta) -> Base ( NonEmpty delta) Source #
Ord a => Delta ( DeltaSet a) Source #
Instance details Defined in Data.Delta Associated Types type Base ( DeltaSet a) Source # Methods apply :: DeltaSet a -> Base ( DeltaSet a) -> Base ( DeltaSet a) Source #
Ord a => Delta ( DeltaSet1 a) Source #
Instance details Defined in Data.Delta Associated Types type Base ( DeltaSet1 a) Source # Methods apply :: DeltaSet1 a -> Base ( DeltaSet1 a) -> Base ( DeltaSet1 a) Source #
Delta ( DeltaList a) Source #
Instance details Defined in Data.Delta Associated Types type Base ( DeltaList a) Source # Methods apply :: DeltaList a -> Base ( DeltaList a) -> Base ( DeltaList a) Source #
Delta ( Replace a) Source #
Instance details Defined in Data.Delta Associated Types type Base ( Replace a) Source # Methods apply :: Replace a -> Base ( Replace a) -> Base ( Replace a) Source #
Delta ( NoChange a) Source #
Instance details Defined in Data.Delta Associated Types type Base ( NoChange a) Source # Methods apply :: NoChange a -> Base ( NoChange a) -> Base ( NoChange a) Source #
Delta ( DeltaTable row) Source #
Instance details Defined in Data.Table Associated Types type Base ( DeltaTable row) Source # Methods apply :: DeltaTable row -> Base ( DeltaTable row) -> Base ( DeltaTable row) Source #
( Delta d1, Delta d2) => Delta (d1, d2) Source #	A pair of deltas represents a delta for a pair.
Instance details Defined in Data.Delta Associated Types type Base (d1, d2) Source # Methods apply :: (d1, d2) -> Base (d1, d2) -> Base (d1, d2) Source #
( Ord key, Delta da) => Delta ( DeltaMap key da) Source #
Instance details Defined in Data.DeltaMap Associated Types type Base ( DeltaMap key da) Source # Methods apply :: DeltaMap key da -> Base ( DeltaMap key da) -> Base ( DeltaMap key da) Source #
key ~ Int => Delta ( DeltaDB key row) Source #
Instance details Defined in Data.Table Associated Types type Base ( DeltaDB key row) Source # Methods apply :: DeltaDB key row -> Base ( DeltaDB key row) -> Base ( DeltaDB key row) Source #
( Ord node, Semigroup edge) => Delta ( DeltaChain node edge) Source #
Instance details Defined in Data.Chain Associated Types type Base ( DeltaChain node edge) Source # Methods apply :: DeltaChain node edge -> Base ( DeltaChain node edge) -> Base ( DeltaChain node edge) Source #
( Delta d1, Delta d2, Delta d3) => Delta (d1, d2, d3) Source #	A triple of deltas represents a delta for a triple.
Instance details Defined in Data.Delta Associated Types type Base (d1, d2, d3) Source # Methods apply :: (d1, d2, d3) -> Base (d1, d2, d3) -> Base (d1, d2, d3) Source #
( Delta d1, Delta d2, Delta d3, Delta d4) => Delta (d1, d2, d3, d4) Source #	A 4-tuple of deltas represents a delta for a 4-tuple.
Instance details Defined in Data.Delta Associated Types type Base (d1, d2, d3, d4) Source # Methods apply :: (d1, d2, d3, d4) -> Base (d1, d2, d3, d4) -> Base (d1, d2, d3, d4) Source #

data NoChange a Source #

Trivial delta encoding for the type a that admits no change at all.

Constructors

NoChange

Instances

Instances details

Eq ( NoChange a) Source #
Instance details Defined in Data.Delta Methods (==) :: NoChange a -> NoChange a -> Bool Source # (/=) :: NoChange a -> NoChange a -> Bool Source #
Ord ( NoChange a) Source #
Instance details Defined in Data.Delta Methods compare :: NoChange a -> NoChange a -> Ordering Source # (<) :: NoChange a -> NoChange a -> Bool Source # (<=) :: NoChange a -> NoChange a -> Bool Source # (>) :: NoChange a -> NoChange a -> Bool Source # (>=) :: NoChange a -> NoChange a -> Bool Source # max :: NoChange a -> NoChange a -> NoChange a Source # min :: NoChange a -> NoChange a -> NoChange a Source #
Show ( NoChange a) Source #
Instance details Defined in Data.Delta Methods showsPrec :: Int -> NoChange a -> ShowS Source # show :: NoChange a -> String Source # showList :: [ NoChange a] -> ShowS Source #
Delta ( NoChange a) Source #
Instance details Defined in Data.Delta Associated Types type Base ( NoChange a) Source # Methods apply :: NoChange a -> Base ( NoChange a) -> Base ( NoChange a) Source #
type Base ( NoChange a) Source #
Instance details Defined in Data.Delta type Base ( NoChange a) = a

newtype Replace a Source #

Trivial delta encoding for the type a that replaces the value wholesale.

Constructors

Replace a

Instances

Instances details

Eq a => Eq ( Replace a) Source #
Instance details Defined in Data.Delta Methods (==) :: Replace a -> Replace a -> Bool Source # (/=) :: Replace a -> Replace a -> Bool Source #
Ord a => Ord ( Replace a) Source #
Instance details Defined in Data.Delta Methods compare :: Replace a -> Replace a -> Ordering Source # (<) :: Replace a -> Replace a -> Bool Source # (<=) :: Replace a -> Replace a -> Bool Source # (>) :: Replace a -> Replace a -> Bool Source # (>=) :: Replace a -> Replace a -> Bool Source # max :: Replace a -> Replace a -> Replace a Source # min :: Replace a -> Replace a -> Replace a Source #
Show a => Show ( Replace a) Source #
Instance details Defined in Data.Delta Methods showsPrec :: Int -> Replace a -> ShowS Source # show :: Replace a -> String Source # showList :: [ Replace a] -> ShowS Source #
Semigroup ( Replace a) Source #	Combine replacements. The first argument takes precedence. In this way, `apply` becomes a `Semigroup` morphism.
Instance details Defined in Data.Delta Methods (<>) :: Replace a -> Replace a -> Replace a Source # sconcat :: NonEmpty ( Replace a) -> Replace a Source # stimes :: Integral b => b -> Replace a -> Replace a Source #
Delta ( Replace a) Source #
Instance details Defined in Data.Delta Associated Types type Base ( Replace a) Source # Methods apply :: Replace a -> Base ( Replace a) -> Base ( Replace a) Source #
type Base ( Replace a) Source #
Instance details Defined in Data.Delta type Base ( Replace a) = a

data DeltaList a Source #

Delta encoding for lists where a list of elements is prepended.

Constructors

Append [a]

Instances

Instances details

Eq a => Eq ( DeltaList a) Source #
Instance details Defined in Data.Delta Methods (==) :: DeltaList a -> DeltaList a -> Bool Source # (/=) :: DeltaList a -> DeltaList a -> Bool Source #
Ord a => Ord ( DeltaList a) Source #
Instance details Defined in Data.Delta Methods compare :: DeltaList a -> DeltaList a -> Ordering Source # (<) :: DeltaList a -> DeltaList a -> Bool Source # (<=) :: DeltaList a -> DeltaList a -> Bool Source # (>) :: DeltaList a -> DeltaList a -> Bool Source # (>=) :: DeltaList a -> DeltaList a -> Bool Source # max :: DeltaList a -> DeltaList a -> DeltaList a Source # min :: DeltaList a -> DeltaList a -> DeltaList a Source #
Show a => Show ( DeltaList a) Source #
Instance details Defined in Data.Delta Methods showsPrec :: Int -> DeltaList a -> ShowS Source # show :: DeltaList a -> String Source # showList :: [ DeltaList a] -> ShowS Source #
Delta ( DeltaList a) Source #
Instance details Defined in Data.Delta Associated Types type Base ( DeltaList a) Source # Methods apply :: DeltaList a -> Base ( DeltaList a) -> Base ( DeltaList a) Source #
type Base ( DeltaList a) Source #
Instance details Defined in Data.Delta type Base ( DeltaList a) = [a]

data DeltaSet1 a Source #

Delta encoding for Set where a single element is deleted or added.

Constructors

Insert a
Delete a

Instances

Instances details

Eq a => Eq ( DeltaSet1 a) Source #
Instance details Defined in Data.Delta Methods (==) :: DeltaSet1 a -> DeltaSet1 a -> Bool Source # (/=) :: DeltaSet1 a -> DeltaSet1 a -> Bool Source #
Ord a => Ord ( DeltaSet1 a) Source #
Instance details Defined in Data.Delta Methods compare :: DeltaSet1 a -> DeltaSet1 a -> Ordering Source # (<) :: DeltaSet1 a -> DeltaSet1 a -> Bool Source # (<=) :: DeltaSet1 a -> DeltaSet1 a -> Bool Source # (>) :: DeltaSet1 a -> DeltaSet1 a -> Bool Source # (>=) :: DeltaSet1 a -> DeltaSet1 a -> Bool Source # max :: DeltaSet1 a -> DeltaSet1 a -> DeltaSet1 a Source # min :: DeltaSet1 a -> DeltaSet1 a -> DeltaSet1 a Source #
Show a => Show ( DeltaSet1 a) Source #
Instance details Defined in Data.Delta Methods showsPrec :: Int -> DeltaSet1 a -> ShowS Source # show :: DeltaSet1 a -> String Source # showList :: [ DeltaSet1 a] -> ShowS Source #
Ord a => Delta ( DeltaSet1 a) Source #
Instance details Defined in Data.Delta Associated Types type Base ( DeltaSet1 a) Source # Methods apply :: DeltaSet1 a -> Base ( DeltaSet1 a) -> Base ( DeltaSet1 a) Source #
type Base ( DeltaSet1 a) Source #
Instance details Defined in Data.Delta type Base ( DeltaSet1 a) = Set a

data DeltaSet a Source #

Delta encoding for a Set where collections of elements are inserted or deleted.

Instances

Instances details

Eq a => Eq ( DeltaSet a) Source #
Instance details Defined in Data.Delta Methods (==) :: DeltaSet a -> DeltaSet a -> Bool Source # (/=) :: DeltaSet a -> DeltaSet a -> Bool Source #
Ord a => Semigroup ( DeltaSet a) Source #	`apply` distributes over `(<>)` .
Instance details Defined in Data.Delta Methods (<>) :: DeltaSet a -> DeltaSet a -> DeltaSet a Source # sconcat :: NonEmpty ( DeltaSet a) -> DeltaSet a Source # stimes :: Integral b => b -> DeltaSet a -> DeltaSet a Source #
Ord a => Monoid ( DeltaSet a) Source #
Instance details Defined in Data.Delta Methods mempty :: DeltaSet a Source # mappend :: DeltaSet a -> DeltaSet a -> DeltaSet a Source # mconcat :: [ DeltaSet a] -> DeltaSet a Source #
Ord a => Delta ( DeltaSet a) Source #
Instance details Defined in Data.Delta Associated Types type Base ( DeltaSet a) Source # Methods apply :: DeltaSet a -> Base ( DeltaSet a) -> Base ( DeltaSet a) Source #
type Base ( DeltaSet a) Source #
Instance details Defined in Data.Delta type Base ( DeltaSet a) = Set a

mkDeltaSet :: Ord a => Set a -> Set a -> DeltaSet a Source #

Delta to get from the second argument to the first argument.

deltaSetToList :: DeltaSet a -> [ DeltaSet1 a] Source #

Flatten a DeltaSet to a list of DeltaSet1 .

In the result list, the set of a appearing as Insert a is disjoint from the set of a appearing as Delete a .

deltaSetFromList :: Ord a => [ DeltaSet1 a] -> DeltaSet a Source #

Collect insertions or deletions of elements into a DeltaSet .

To save space, combinations of Insert and Delete for the same element are simplified when possible. These simplifications always preserve the property

apply (deltaSetFromList ds) = apply ds

Embedding of types and delta encodings

An Embedding da db embeds one type and its delta encoding da into another type and its delta encoding db .

For reasons of efficiency, Embedding is an abstract type. It is constructed using the Embedding' type, which has three components.

write embeds values from the type a = Base da into the type b = Base bd .
load attempts to retrieve the value of type a from the type b , but does not necessarily succeed.
update maps a delta encoding da to a delta encoding db . For this mapping, the value of type a and a corresponding value of type b are provided; the delta encodings of types da and db are relative to these values.

The embedding of one type into the other is characterized by the following properties:

The embedding need not be surjective : The type b may contain many values that do not correspond to a value of type a . Hence, load has an Either result. (See Note [EitherSomeException] for the choice of exception type.) However, retrieving a written value always succeeds, we have
```
load . write = Right
```
The embedding is redundant : The type b may contain multiple values that correspond to one and the same a . This is why the update function expects the type b as argument, so that the right delta encoding can be computed. Put differently, we often have
```
write a ≠ b   where Right a = load b
```

The embedding of delta encoding commutes with apply . We have

Just (apply da a) = load (apply (update a b da) b)
    where Right a = load b

However, since the embedding is redundant, we often have

apply (update a (write a) da) (write a) ≠ write (apply da a)

data Embedding da db Source #

Embedding with efficient composition o . To construct an embedding, use mkEmbedding .

Instances

Instances details

Semigroupoid Embedding Source #	Efficient composition of `Embedding`
Instance details Defined in Data.Delta Methods o :: forall (j :: k) (k1 :: k) (i :: k). Embedding j k1 -> Embedding i j -> Embedding i k1 Source #

class Semigroupoid (c :: k -> k -> Type ) where Source #

Category sans id

Methods

o :: forall (j :: k) (k1 :: k) (i :: k). c j k1 -> c i j -> c i k1 Source #

Instances

Instances details

Semigroupoid ( Coercion :: k -> k -> Type )
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k0) (k1 :: k0) (i :: k0). Coercion j k1 -> Coercion i j -> Coercion i k1 Source #
Semigroupoid ( (:~:) :: k -> k -> Type )
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k0) (k1 :: k0) (i :: k0). (j :~: k1) -> (i :~: j) -> i :~: k1 Source #
Semigroupoid ( (:~~:) :: k -> k -> Type )
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k0) (k1 :: k0) (i :: k0). (j :~~: k1) -> (i :~~: j) -> i :~~: k1 Source #
Category k2 => Semigroupoid ( WrappedCategory k2 :: k1 -> k1 -> Type )
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k) (k10 :: k) (i :: k). WrappedCategory k2 j k10 -> WrappedCategory k2 i j -> WrappedCategory k2 i k10 Source #
Semigroup m => Semigroupoid ( Semi m :: k -> k -> Type )
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k0) (k1 :: k0) (i :: k0). Semi m j k1 -> Semi m i j -> Semi m i k1 Source #
Semigroupoid (,)	http://en.wikipedia.org/wiki/Band_(mathematics)#Rectangular_bands
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k) (k1 :: k) (i :: k). (j, k1) -> (i, j) -> (i, k1) Source #
Semigroupoid Op
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k) (k1 :: k) (i :: k). Op j k1 -> Op i j -> Op i k1 Source #
Semigroupoid Machine Source #	Composition of `Machine`
Instance details Defined in Data.Delta Methods o :: forall (j :: k) (k1 :: k) (i :: k). Machine j k1 -> Machine i j -> Machine i k1 Source #
Semigroupoid Embedding Source #	Efficient composition of `Embedding`
Instance details Defined in Data.Delta Methods o :: forall (j :: k) (k1 :: k) (i :: k). Embedding j k1 -> Embedding i j -> Embedding i k1 Source #
Bind m => Semigroupoid ( Kleisli m :: Type -> Type -> Type )
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k) (k1 :: k) (i :: k). Kleisli m j k1 -> Kleisli m i j -> Kleisli m i k1 Source #
Semigroupoid ( Const :: Type -> Type -> Type )
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k) (k1 :: k) (i :: k). Const j k1 -> Const i j -> Const i k1 Source #
Semigroupoid ( Tagged :: Type -> Type -> Type )
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k) (k1 :: k) (i :: k). Tagged j k1 -> Tagged i j -> Tagged i k1 Source #
Semigroupoid ((->) :: Type -> Type -> Type )
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k) (k1 :: k) (i :: k). (j -> k1) -> (i -> j) -> i -> k1 Source #
Extend w => Semigroupoid ( Cokleisli w :: Type -> Type -> Type )
Instance details Defined in Data.Semigroupoid Methods o :: forall (j :: k) (k1 :: k) (i :: k). Cokleisli w j k1 -> Cokleisli w i j -> Cokleisli w i k1 Source #

data Embedding' da db where Source #

Specification of an embedding of a type a with delta encoding da into the type b with delta encoding db . See the discussion of Embedding for a more detailed description.

Constructors

Embedding'
Fields :: ( Delta da, Delta db, a ~ Base da, b ~ Base db) => { load :: b -> Either SomeException a , write :: a -> b , update :: a -> b -> da -> db } -> Embedding' da db

mkEmbedding :: Embedding' da db -> Embedding da db Source #

Construct Embedding with efficient composition

fromEmbedding :: ( Delta da, Delta db) => Embedding da db -> Embedding' da db Source #

Extract load , write , and update functions from an efficient Embedding .

pair :: Embedding da1 db1 -> Embedding da2 db2 -> Embedding (da1, da2) (db1, db2) Source #

A pair of Embedding s gives an embedding of pairs.

liftUpdates Source #

Arguments

:: Delta da
=> Embedding da db
-> [da]	List of deltas to apply. The `head` is applied last .
-> Base da	Base value to apply the deltas to.
-> ( Base db, [db])	(Final base value, updates that were applied ( `head` is last )).

Lift a sequence of updates through an Embedding .

replaceFromApply :: ( Delta da, a ~ Base da) => Embedding' da ( Replace a) Source #

Having an apply function is equivalent to the existence of a canonical embedding into the trivial Replace delta encoding.

Internal

inject :: Embedding da db -> Base da -> Machine da db Source #

project :: Embedding da db -> Base db -> Either SomeException ( Base da, Machine da db) Source #

data Machine da db Source #

Strict pair. If a value of this type is in WHNF, so are the two components. data StrictPair a b = !a :*: !b infixr 1 :*:

A state machine that maps deltas to deltas. This machine always carries a state of type Base db around.

Constructors

Machine
Fields state_ :: !( Base db) step_ :: ( Base da, da) -> (db, Machine da db)

Instances

Instances details

Semigroupoid Machine Source #	Composition of `Machine`
Instance details Defined in Data.Delta Methods o :: forall (j :: k) (k1 :: k) (i :: k). Machine j k1 -> Machine i j -> Machine i k1 Source #

idle :: Delta da => Base da -> Machine da da Source #

Identity machine starting from a base type.

pairMachine :: Machine da1 db1 -> Machine da2 db2 -> Machine (da1, da2) (db1, db2) Source #

Pair two Machine .

fromState :: Delta db => (( Base da, da) -> ( Base db, s) -> (db, s)) -> ( Base db, s) -> Machine da db Source #

Create a Machine from a specific state s , and the built-in state Base db .