Data.FixFile

A FixFile is file for storing recursive data. The file supports MVCC through an append-only file.

In order to eliminate distinctions between data structures that are file-backed versus in-memory, this library makes heavy use of lazy IO. Transactions are used to ensure safety of the unsafe IO.

The data structures used by a FixFile should not be recursive directly, but should have instances of Typeable, Traversable, and Serialize and should be structured such that the fixed point of the data type is recursive.

There is also the concept of the Root data of a FixFile. This can be used as a kind of header for a FixFile that can allow several recursive data structures to be modified in a single transaction.

Fixed point combinators

class Fixed g where

Fixed is a typeclass for representing the fixed point of a Functor. A well-behaved instance of Fixed should not change the shape of the underlying Functor.

In other words, the following should always be true: outf (inf x) == x

Minimal complete definition

inf, outf

Methods

inf :: f (g f) -> g f

outf :: g f -> f (g f)

Instances

Fixed Fix

Methods

inf :: f (Fix f) -> Fix f

outf :: Fix f -> f (Fix f)

Fixed (Stored s)

Methods

inf :: f (Stored s f) -> Stored s f

outf :: Stored s f -> f (Stored s f)

newtype Fix f

Fix is a type for creating an in-memory representation of the fixed point of a Functor.

Constructors

InF

Fields

• outF :: f (Fix f)

Instances

Fixed Fix

Methods

inf :: f (Fix f) -> Fix f

outf :: Fix f -> f (Fix f)

data Stored s f

Stored is a fixed-point combinator of f in Transaction s.

Instances

Fixed (Stored s)

Methods

inf :: f (Stored s f) -> Stored s f

outf :: Stored s f -> f (Stored s f)

MonadState (r (Stored s)) (Transaction r s)

Methods

get :: Transaction r s (r (Stored s))

put :: r (Stored s) -> Transaction r s ()

state :: (r (Stored s) -> (a, r (Stored s))) -> Transaction r s a

Null typeclasses

class Null f where

Null is a typeclass for representing data that can be empty as well as the null predicate that can determine if a piece of data is empty.

Minimal complete definition

empty, null

Methods

empty :: f

null :: f -> Bool

Instances

(Fixed g, Null1 f) => Null (g f)

Methods

empty :: g f

null :: g f -> Bool

Null1 f => Null (f a)

Methods

empty :: f a

null :: f a -> Bool

class Null1 f where

Null1 is for expressing null types of kind (* -> *).

Minimal complete definition

empty1, null1

Methods

empty1 :: f a

null1 :: f a -> Bool

Instances

Null1 []

Methods

empty1 :: [a]

null1 :: [a] -> Bool

Null1 Maybe

Methods

empty1 :: Maybe a

null1 :: Maybe a -> Bool

Null1 (Set i)

Methods

empty1 :: Set i a

null1 :: Set i a -> Bool

Null1 (Trie v)

Methods

empty1 :: Trie v a

null1 :: Trie v a -> Bool

Null1 (Trie v)

Methods

empty1 :: Trie v a

null1 :: Trie v a -> Bool

Null1 (BTree n k v)

Methods

empty1 :: BTree n k v a

null1 :: BTree n k v a -> Bool

Null1 (BTree n k v)

Methods

empty1 :: BTree n k v a

null1 :: BTree n k v a -> Bool

F-Algebras

type CataAlg f a = f a -> a

CataAlg is a catamorphism F-Algebra.

type CataMAlg m f a = f a -> m a

CataMAlg is a monadic catamorphism F-Algebra.

cata :: (Functor f, Fixed g) => CataAlg f a -> g f -> a

cata applies a CataAlg over a fixed point of a Functor.

cataM :: (Traversable f, Fixed g, Monad m) => CataMAlg m f a -> g f -> m a

cataM is a monadic catamorphism.

type AnaAlg f a = a -> f a

AnaAlg is an anamorpism F-Algebra.

type AnaMAlg m f a = a -> m (f a)

AnaMAlg is a monadic anamorpism F-Algebra.

ana :: (Functor f, Fixed g) => AnaAlg f a -> a -> g f

ana applies an AnaAlg over an argument to produce a fixed-point of a Functor.

anaM :: (Traversable f, Fixed g, Monad m) => AnaMAlg m f a -> a -> m (g f)

anaM is a monadic anamorphism.

type ParaAlg g f a = f (g f, a) -> a

ParaAlg is a paramorphism F-Algebra.

type ParaMAlg m g f a = f (g f, a) -> m a

ParaAlg is a monadic paramorphism F-Algebra.

para :: (Functor f, Fixed g) => ParaAlg g f a -> g f -> a

para applies a ParaAlg over a fixed point of a Functor.

paraM :: (Traversable f, Fixed g, Monad m) => ParaMAlg m g f a -> g f -> m a

paraM is a monadic paramorphism.

hylo :: Functor f => AnaAlg f a -> CataAlg f b -> a -> b

hylo combines ana and cata into a single operation.

hyloM :: (Traversable f, Monad m) => AnaMAlg m f a -> CataMAlg m f b -> a -> m b

hyloM is a monadic hylomorphism.

iso :: (Functor f, Fixed g, Fixed h) => g f -> h f

iso maps from a fixed point of a Functor to a different fixed point of the same Functor. For any two well-behaved instances of Fixed, the shape of the Functor should remain unchanged.

Fixed Typeclasses

class FixedAlg f

FixedAlg is a typeclass for describing the relationship between a Functor that is used with a Fixed combinator and an algebraic datatype in that Functor other than the one used for fixed-point recursion.

Associated Types

type Alg f :: *

Instances

FixedAlg (Set i)

Associated Types

type Alg (Set i :: * -> *) :: *

FixedAlg (Tree23 (Map k v))

Associated Types

type Alg (Tree23 (Map k v) :: * -> *) :: *

FixedAlg (Tree23 (Set k))

Associated Types

type Alg (Tree23 (Set k) :: * -> *) :: *

FixedAlg (Trie v)

Associated Types

type Alg (Trie v :: * -> *) :: *

FixedAlg (Trie v)

Associated Types

type Alg (Trie v :: * -> *) :: *

FixedAlg (BTree n k v)

Associated Types

type Alg (BTree n k v :: * -> *) :: *

FixedAlg (BTree n k v)

Associated Types

type Alg (BTree n k v :: * -> *) :: *

class FixedAlg f => FixedSub f

FixedSub is a typeclass for describing the relationship between a FixedAlg Functor f and that same Functor with Alg f switched from v to v'.

Associated Types

type Sub f v v' :: * -> *

Instances

FixedSub (Tree23 (Map k v))

Associated Types

type Sub (Tree23 (Map k v) :: * -> *) v v' :: * -> *

FixedSub (Trie v)

Associated Types

type Sub (Trie v :: * -> *) v v' :: * -> *

FixedSub (Trie v)

Associated Types

type Sub (Trie v :: * -> *) v v' :: * -> *

FixedSub (BTree n k v)

Associated Types

type Sub (BTree n k v :: * -> *) v v' :: * -> *

FixedSub (BTree n k v)

Associated Types

type Sub (BTree n k v :: * -> *) v v' :: * -> *

class FixedSub f => FixedFunctor f where

FixedFunctor is a typeclass for describing mapping behavior for datatypes used with Fixed combinators.

Minimal complete definition

fmapF

Methods

fmapF :: (Fixed g, Fixed g', a ~ Alg f) => (a -> b) -> g f -> g' (Sub f a b)

Map over a Fixed recursive FixedSub f.

Instances

FixedFunctor (Tree23 (Map k v))

Methods

fmapF :: (Fixed g, Fixed g', (* ~ a) (Alg (Tree23 (Map k v)))) => (a -> b) -> g (Tree23 (Map k v)) -> g' (Sub (Tree23 (Map k v)) a b)

FixedFunctor (Trie v)

Methods

fmapF :: (Fixed g, Fixed g', (* ~ a) (Alg (Trie v))) => (a -> b) -> g (Trie v) -> g' (Sub (Trie v) a b)

FixedFunctor (Trie v)

Methods

fmapF :: (Fixed g, Fixed g', (* ~ a) (Alg (Trie v))) => (a -> b) -> g (Trie v) -> g' (Sub (Trie v) a b)

FixedFunctor (BTree n k v)

Methods

fmapF :: (Fixed g, Fixed g', (* ~ a) (Alg (BTree n k v))) => (a -> b) -> g (BTree n k v) -> g' (Sub (BTree n k v) a b)

FixedFunctor (BTree n k v)

Methods

fmapF :: (Fixed g, Fixed g', (* ~ a) (Alg (BTree n k v))) => (a -> b) -> g (BTree n k v) -> g' (Sub (BTree n k v) a b)

fmapF' :: (FixedFunctor f, Fixed g, a ~ Alg f) => (a -> b) -> g f -> g (Sub f a b)

fmapF, but using a single instance of Fixed.

class FixedAlg f => FixedFoldable f where

FixedFoldable is a typeclass for describing folds over datatypes with Fixed combinators.

Minimal complete definition

foldMapF

Methods

foldMapF :: (Fixed g, Monoid m, a ~ Alg f) => (a -> m) -> g f -> m

Fold over a Fixed recursive FixedAlg f.

Instances

FixedFoldable (Set i)

Methods

foldMapF :: (Fixed g, Monoid m, (* ~ a) (Alg (Set i))) => (a -> m) -> g (Set i) -> m

FixedFoldable (Tree23 (Map k v))

Methods

foldMapF :: (Fixed g, Monoid m, (* ~ a) (Alg (Tree23 (Map k v)))) => (a -> m) -> g (Tree23 (Map k v)) -> m

FixedFoldable (Tree23 (Set k))

Methods

foldMapF :: (Fixed g, Monoid m, (* ~ a) (Alg (Tree23 (Set k)))) => (a -> m) -> g (Tree23 (Set k)) -> m

FixedFoldable (Trie v)

Methods

foldMapF :: (Fixed g, Monoid m, (* ~ a) (Alg (Trie v))) => (a -> m) -> g (Trie v) -> m

FixedFoldable (Trie v)

Methods

foldMapF :: (Fixed g, Monoid m, (* ~ a) (Alg (Trie v))) => (a -> m) -> g (Trie v) -> m

FixedFoldable (BTree n k v)

Methods

foldMapF :: (Fixed g, Monoid m, (* ~ a) (Alg (BTree n k v))) => (a -> m) -> g (BTree n k v) -> m

FixedFoldable (BTree n k v)

Methods

foldMapF :: (Fixed g, Monoid m, (* ~ a) (Alg (BTree n k v))) => (a -> m) -> g (BTree n k v) -> m

class FixedSub f => FixedTraversable f where

FixedTraversable is a typeclass for describing traversals over datatypes with Fixed combinators.

Minimal complete definition

traverseF

Methods

traverseF :: (Fixed g, Fixed g', Applicative h, a ~ Alg f) => (a -> h b) -> g f -> h (g' (Sub f a b))

Traverse over a Fixed recursive FixedSub f in the Applicative h.

Instances

FixedTraversable (Tree23 (Map k v))

Methods

traverseF :: (Fixed g, Fixed g', Applicative h, (* ~ a) (Alg (Tree23 (Map k v)))) => (a -> h b) -> g (Tree23 (Map k v)) -> h (g' (Sub (Tree23 (Map k v)) a b))

FixedTraversable (Trie v)

Methods

traverseF :: (Fixed g, Fixed g', Applicative h, (* ~ a) (Alg (Trie v))) => (a -> h b) -> g (Trie v) -> h (g' (Sub (Trie v) a b))

FixedTraversable (Trie v)

Methods

traverseF :: (Fixed g, Fixed g', Applicative h, (* ~ a) (Alg (Trie v))) => (a -> h b) -> g (Trie v) -> h (g' (Sub (Trie v) a b))

FixedTraversable (BTree n k v)

Methods

traverseF :: (Fixed g, Fixed g', Applicative h, (* ~ a) (Alg (BTree n k v))) => (a -> h b) -> g (BTree n k v) -> h (g' (Sub (BTree n k v) a b))

FixedTraversable (BTree n k v)

Methods

traverseF :: (Fixed g, Fixed g', Applicative h, (* ~ a) (Alg (BTree n k v))) => (a -> h b) -> g (BTree n k v) -> h (g' (Sub (BTree n k v) a b))

traverseF' :: (FixedTraversable f, Fixed g, Applicative h, a ~ Alg f) => (a -> h b) -> g f -> h (g (Sub f a b))

traverseF, but using a single instance of Fixed.

Root Data

type Fixable f = (Traversable f, Serialize (f (Ptr f)), Typeable f, Null1 f)

A Constraint for data that can be used with a Ref

class FixTraverse t where

FixTraverse is a class based on Traverse but taking an argument of kind ((* -> *) -> *) instead of *.

Minimal complete definition

traverseFix

Methods

traverseFix :: Applicative f => (forall g. Fixable g => a g -> f (b g)) -> t a -> f (t b)

Given a function that maps from a to b over Fixable g in the Applicative f, traverse over t changing the fixed-point combinator from a to b.

Instances

Fixable f => FixTraverse (Ref f)

Methods

traverseFix :: Applicative f => (forall g. Fixable g => a g -> f (b g)) -> Ref f a -> f (Ref f b)

type Root r = (FixTraverse r, Serialize (r Ptr))

A Root is a datastructure that is an instance of FixTraverse and Serialize. This acts as a sort of "header" for the file where the Root may have several Refs under it to different Functors.

data Ptr f

A Ptr points to a location in a FixFile and has a phantom type for a Functor f. A Root expects an argument that resembles a Fixed, but we can pass it a Ptr instead. This is not a well-formed Fixed because it can't be unpacked into f (Ptr f).

But, it can be serialized, which allows a Root object that takes this as an argument to be serialized.

Instances

Eq (Ptr f)

Methods

(==) :: Ptr f -> Ptr f -> Bool

(/=) :: Ptr f -> Ptr f -> Bool

Ord (Ptr f)

Methods

compare :: Ptr f -> Ptr f -> Ordering

(<) :: Ptr f -> Ptr f -> Bool

(<=) :: Ptr f -> Ptr f -> Bool

(>) :: Ptr f -> Ptr f -> Bool

(>=) :: Ptr f -> Ptr f -> Bool

max :: Ptr f -> Ptr f -> Ptr f

min :: Ptr f -> Ptr f -> Ptr f

Read (Ptr f)

Methods

readsPrec :: Int -> ReadS (Ptr f)

readList :: ReadS [Ptr f]

readPrec :: ReadPrec (Ptr f)

readListPrec :: ReadPrec [Ptr f]

Show (Ptr f)

Methods

showsPrec :: Int -> Ptr f -> ShowS

show :: Ptr f -> String

showList :: [Ptr f] -> ShowS

Generic (Ptr f)

Associated Types

type Rep (Ptr f) :: * -> *

Methods

from :: Ptr f -> Rep (Ptr f) x

to :: Rep (Ptr f) x -> Ptr f

Serialize (Ptr f)

Methods

put :: Putter (Ptr f)

get :: Get (Ptr f)

Hashable (Ptr f)

Methods

hashWithSalt :: Int -> Ptr f -> Int

hash :: Ptr f -> Int

Serialize (Ref f Ptr)

Methods

put :: Putter (Ref f Ptr)

get :: Get (Ref f Ptr)

type Rep (Ptr f)

type Rep (Ptr f)

newtype Ref f g

A Ref is a reference to a Functor f in the Fixed instance of g.

This is an instance of Root and acts to bridge between the Root and the recursively defined data structure that is (g f).

Constructors

Ref

Fields

• deRef :: g f

Instances

Fixable f => FixTraverse (Ref f)

Methods

traverseFix :: Applicative f => (forall g. Fixable g => a g -> f (b g)) -> Ref f a -> f (Ref f b)

Generic (Ref f g)

Associated Types

type Rep (Ref f g) :: * -> *

Methods

from :: Ref f g -> Rep (Ref f g) x

to :: Rep (Ref f g) x -> Ref f g

Serialize (Ref f Ptr)

Methods

put :: Putter (Ref f Ptr)

get :: Get (Ref f Ptr)

type Rep (Ref f g)

type Rep (Ref f g) = D1 (MetaData "Ref" "Data.FixFile" "fixfile-0.7.0.0-71ntBbEspJw1TxxxS3z50O" True) (C1 (MetaCons "Ref" PrefixI True) (S1 (MetaSel (Just Symbol "deRef") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 (g f))))

ref :: Lens' (Ref f g) (g f)

Lens for accessing the value stored in a Ref

FixFiles

data FixFile r

A FixFile is a handle for accessing a file-backed recursive data structure. r is the Root object stored in the FixFile.

createFixFile :: Root r => r Fix -> FilePath -> IO (FixFile r)

Create a FixFile, using Fix f as the initial structure to store at the location described by FilePath.

createFixFileHandle :: Root r => r Fix -> FilePath -> Handle -> IO (FixFile r)

Create a FixFile, using Fix f as the initial structure to store at the location described by FilePath and using the Handle to the file to be created.

openFixFile :: Serialize (r Ptr) => FilePath -> IO (FixFile r)

Open a FixFile from the file described by FilePath.

openFixFileHandle :: Serialize (r Ptr) => FilePath -> Handle -> IO (FixFile r)

Open a FixFile from the file described by FilePath and using the Handle to the file.

closeFixFile :: FixFile r -> IO ()

Close a FixFile. This can potentially cause errors on data that is lazily being read from a Transaction.

fixFilePath :: FixFile r -> FilePath

Get the FilePath of a FixFile.

clone :: Root r => FilePath -> FixFile r -> IO ()

It's potentially useful to copy the contents of a FixFile to a new location as a backup. The clone function essentially runs vacuum on a FixFile, but writes the output to the specified path.

cloneH :: Root r => FixFile r -> Handle -> IO ()

cloneH is clone but taking a Handle as an argument instead of a FilePath.

vacuum :: Root r => FixFile r -> IO ()

Because a FixFile is backed by an append-only file, there is a periodic need to vacuum the file to garbage collect data that is no longer referenced from the root. This task operates on a temporary file that then replaces the file that backs FixFile.

The memory usage of this operation scales with the recursive depth of the structure stored in the file.

Transactions

data Transaction r s a

A Transaction is an isolated execution of a read or update operation on the root object stored in a FixFile. r is the Root data that is stored by the FixFile. s is a phantom type used to isolate Stored values to the transaction where they are run.

Instances

MonadState (r (Stored s)) (Transaction r s)

Methods

get :: Transaction r s (r (Stored s))

put :: r (Stored s) -> Transaction r s ()

state :: (r (Stored s) -> (a, r (Stored s))) -> Transaction r s a

Monad (Transaction f s)

Methods

(>>=) :: Transaction f s a -> (a -> Transaction f s b) -> Transaction f s b

(>>) :: Transaction f s a -> Transaction f s b -> Transaction f s b

return :: a -> Transaction f s a

fail :: String -> Transaction f s a

Functor (Transaction f s)

Methods

fmap :: (a -> b) -> Transaction f s a -> Transaction f s b

(<$) :: a -> Transaction f s b -> Transaction f s a

Applicative (Transaction f s)

Methods

pure :: a -> Transaction f s a

(<*>) :: Transaction f s (a -> b) -> Transaction f s a -> Transaction f s b

(*>) :: Transaction f s a -> Transaction f s b -> Transaction f s b

(<*) :: Transaction f s a -> Transaction f s b -> Transaction f s a

alterT :: (tr ~ Transaction (Ref f) s, Traversable f, Serialize (f (Ptr f))) => (Stored s f -> Stored s f) -> tr ()

The preferred way to modify the root object of a FixFile is by using alterT. It applies a function that takes the root object as a Stored s f and returns the new desired head of the same type.

lookupT :: (tr ~ Transaction (Ref f) s, Traversable f, Serialize (f (Ptr f))) => (Stored s f -> a) -> tr a

The preferred way to read from a FixFile is to use lookupT. It applies a function that takes a Stored s f and returns a value.

readTransaction :: Root r => FixFile r -> (forall s. Transaction r s a) -> IO a

Perform a read transaction on a FixFile. This transaction cannot modify the root object stored in the file. The returned value is lazily evaluated, but will always correspond to the root object at the start of the transaction.

writeTransaction :: Root r => FixFile r -> (forall s. Transaction r s a) -> IO a

Perform a write transaction on a FixFile. This operation differs from the readTransaction in that the root object stored in the file can potentially be updated by this Transaction.

writeExceptTransaction :: Root r => FixFile r -> (forall s. ExceptT e (Transaction r s) a) -> IO (Either e a)

The writeExceptTransaction function behaves like writeTransaction, but applies to a Transaction wrapped in ExceptT. In the event that an exception propagates through the Transaction, the updates are not committed to disk.

This is meant to provide a mechanism for aborting Transactions.

subTransaction :: Lens' (r (Stored s)) (r' (Stored s)) -> Transaction r' s a -> Transaction r s a

Perform a Transaction on a part of the root object.

getRoot :: Root r => Transaction r s (r Fix)

Get the root datastructure from the transaction as r Fix.

getFull :: Functor f => Transaction (Ref f) s (Fix f)

Get the full datastructure from the transaction as a Fix f.