free-categories-0.2.0.2: free categories

Copyright(c) Eitan Chatav 2019
Maintainereitan@morphism.tech
Stabilityexperimental
Safe HaskellSafe
LanguageHaskell2010

Control.Category.Free

Description

Consider the category of Haskell Categorys, a subcategory of the category of quivers with,

  • constrained objects Category c => c
  • morphisms are functors (which preserve objects)
  • t :: (Category c, Category d) => c x y -> d x y
  • t id = id
  • t (g . f) = t g . t f

Thus, a functor from quivers to Categorys has (QFunctor c, forall p. Category (c p)) with.

qmap f id = id
qmap f (q . p) = qmap f q . qmap f p

The free category functor from quivers to Categorys may be defined up to isomorphism as

  • the functor Path of type-aligned lists
  • the functor FoldPath of categorical folds
  • abstractly as CFree path => path, the class of left adjoints to the functor which forgets the constraint on Category c => c
  • or as any isomorphic data structure
Synopsis

Documentation

data Path p x y where Source #

A Path with steps in p is a singly linked list of "type-aligned" constructions of p.

>>> :{
let
  path :: Path (->) String Int
  path = length :>> (\x -> x^2) :>> Done
in
  qfold path "hello"
:}
25

Constructors

Done :: Path p x x 
(:>>) :: p x y -> Path p y z -> Path p x z infixr 7 
Instances
QFunctor (Path :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

qmap :: (forall (x :: k0) (y :: k1). p x y -> q x y) -> Path p x y -> Path q x y Source #

QMonad (Path :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

qjoin :: Path (Path p) x y -> Path p x y Source #

qbind :: (forall (x :: k0) (y :: k1). p x y -> Path q x y) -> Path p x y -> Path q x y Source #

QPointed (Path :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

qsingle :: p x y -> Path p x y Source #

QTraversable (Path :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

qtraverse :: Applicative m => (forall (x :: k0) (y :: k0). p x y -> m (q x y)) -> Path p x y -> m (Path q x y) Source #

QFoldable (Path :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

qfoldMap :: Category q => (forall (x :: k0) (y :: k0). p x y -> q x y) -> Path p x y -> q x y Source #

qfold :: Category q => Path q x y -> q x y Source #

qfoldr :: (forall (x :: k0) (y :: k0) (z :: k1). p x y -> q y z -> q x z) -> q y z -> Path p x y -> q x z Source #

qfoldl :: (forall (x :: k0) (y :: k1) (z :: k1). q x y -> p y z -> q x z) -> q x y -> Path p y z -> q x z Source #

qtoMonoid :: Monoid m => (forall (x :: k0) (y :: k0). p x y -> m) -> Path p x y -> m Source #

qtoList :: (forall (x :: k0) (y :: k0). p x y -> a) -> Path p x y -> [a] Source #

qtraverse_ :: (Applicative m, Category q) => (forall (x :: k0) (y :: k0). p x y -> m (q x y)) -> Path p x y -> m (q x y) Source #

CFree (Path :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Category (Path p :: k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

id :: Path p a a #

(.) :: Path p b c -> Path p a b -> Path p a c #

(forall (x1 :: k) (y1 :: k). Show (p x1 y1)) => Show (Path p x y) Source # 
Instance details

Defined in Control.Category.Free

Methods

showsPrec :: Int -> Path p x y -> ShowS #

show :: Path p x y -> String #

showList :: [Path p x y] -> ShowS #

x ~ y => Semigroup (Path p x y) Source # 
Instance details

Defined in Control.Category.Free

Methods

(<>) :: Path p x y -> Path p x y -> Path p x y #

sconcat :: NonEmpty (Path p x y) -> Path p x y #

stimes :: Integral b => b -> Path p x y -> Path p x y #

x ~ y => Monoid (Path p x y) Source # 
Instance details

Defined in Control.Category.Free

Methods

mempty :: Path p x y #

mappend :: Path p x y -> Path p x y -> Path p x y #

mconcat :: [Path p x y] -> Path p x y #

pattern (:<<) :: Path p y z -> p x y -> Path p x z infixl 7 Source #

The snoc pattern for right-to-left composition.

newtype FoldPath p x y Source #

Encodes a path as its qfoldMap function.

Constructors

FoldPath 

Fields

Instances
QFunctor (FoldPath :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

qmap :: (forall (x :: k0) (y :: k1). p x y -> q x y) -> FoldPath p x y -> FoldPath q x y Source #

QMonad (FoldPath :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

qjoin :: FoldPath (FoldPath p) x y -> FoldPath p x y Source #

qbind :: (forall (x :: k0) (y :: k1). p x y -> FoldPath q x y) -> FoldPath p x y -> FoldPath q x y Source #

QPointed (FoldPath :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

qsingle :: p x y -> FoldPath p x y Source #

QTraversable (FoldPath :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

qtraverse :: Applicative m => (forall (x :: k0) (y :: k0). p x y -> m (q x y)) -> FoldPath p x y -> m (FoldPath q x y) Source #

QFoldable (FoldPath :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

qfoldMap :: Category q => (forall (x :: k0) (y :: k0). p x y -> q x y) -> FoldPath p x y -> q x y Source #

qfold :: Category q => FoldPath q x y -> q x y Source #

qfoldr :: (forall (x :: k0) (y :: k0) (z :: k1). p x y -> q y z -> q x z) -> q y z -> FoldPath p x y -> q x z Source #

qfoldl :: (forall (x :: k0) (y :: k1) (z :: k1). q x y -> p y z -> q x z) -> q x y -> FoldPath p y z -> q x z Source #

qtoMonoid :: Monoid m => (forall (x :: k0) (y :: k0). p x y -> m) -> FoldPath p x y -> m Source #

qtoList :: (forall (x :: k0) (y :: k0). p x y -> a) -> FoldPath p x y -> [a] Source #

qtraverse_ :: (Applicative m, Category q) => (forall (x :: k0) (y :: k0). p x y -> m (q x y)) -> FoldPath p x y -> m (q x y) Source #

CFree (FoldPath :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Category (FoldPath p :: k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

id :: FoldPath p a a #

(.) :: FoldPath p b c -> FoldPath p a b -> FoldPath p a c #

x ~ y => Semigroup (FoldPath p x y) Source # 
Instance details

Defined in Control.Category.Free

Methods

(<>) :: FoldPath p x y -> FoldPath p x y -> FoldPath p x y #

sconcat :: NonEmpty (FoldPath p x y) -> FoldPath p x y #

stimes :: Integral b => b -> FoldPath p x y -> FoldPath p x y #

x ~ y => Monoid (FoldPath p x y) Source # 
Instance details

Defined in Control.Category.Free

Methods

mempty :: FoldPath p x y #

mappend :: FoldPath p x y -> FoldPath p x y -> FoldPath p x y #

mconcat :: [FoldPath p x y] -> FoldPath p x y #

class (QPointed c, QFoldable c, forall p. Category (c p)) => CFree c Source #

Unpacking the definition of a left adjoint to the forgetful functor from Categorys to quivers, any

f :: Category d => p x y -> d x y

factors uniquely through the free Category c as

qfoldMap f . qsingle = f
Instances
CFree (FoldPath :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

CFree (Path :: (k -> k -> Type) -> k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

toPath :: (QFoldable c, CFree path) => c p x y -> path p x y Source #

toPath collapses any QFoldable into a CFree. It is the unique isomorphism which exists between any two CFree functors.

reversePath :: (QFoldable c, CFree path) => c p x y -> path (OpQ p) y x Source #

Reverse all the arrows in a path.

beforeAll :: (QFoldable c, CFree path) => (forall x. p x x) -> c p x y -> path p x y Source #

Insert a given loop before each step.

afterAll :: (QFoldable c, CFree path) => (forall x. p x x) -> c p x y -> path p x y Source #

Insert a given loop before each step.

class Category (cat :: k -> k -> Type) where #

A class for categories. Instances should satisfy the laws

f . id  =  f  -- (right identity)
id . f  =  f  -- (left identity)
f . (g . h)  =  (f . g) . h  -- (associativity)

Methods

id :: cat a a #

the identity morphism

(.) :: cat b c -> cat a b -> cat a c infixr 9 #

morphism composition

Instances
Category (Coercion :: k -> k -> Type)

Since: base-4.7.0.0

Instance details

Defined in Control.Category

Methods

id :: Coercion a a #

(.) :: Coercion b c -> Coercion a b -> Coercion a c #

Category ((:~:) :: k -> k -> Type)

Since: base-4.7.0.0

Instance details

Defined in Control.Category

Methods

id :: a :~: a #

(.) :: (b :~: c) -> (a :~: b) -> a :~: c #

Category c => Category (IsoQ c :: k -> k -> Type) Source # 
Instance details

Defined in Data.Quiver

Methods

id :: IsoQ c a a #

(.) :: IsoQ c b c0 -> IsoQ c a b -> IsoQ c a c0 #

Monoid m => Category (ReflQ m :: k -> k -> Type) Source # 
Instance details

Defined in Data.Quiver

Methods

id :: ReflQ m a a #

(.) :: ReflQ m b c -> ReflQ m a b -> ReflQ m a c #

Category ((:~~:) :: k -> k -> Type)

Since: base-4.10.0.0

Instance details

Defined in Control.Category

Methods

id :: a :~~: a #

(.) :: (b :~~: c) -> (a :~~: b) -> a :~~: c #

Category (Path p :: k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

id :: Path p a a #

(.) :: Path p b c -> Path p a b -> Path p a c #

Category (FoldPath p :: k -> k -> Type) Source # 
Instance details

Defined in Control.Category.Free

Methods

id :: FoldPath p a a #

(.) :: FoldPath p b c -> FoldPath p a b -> FoldPath p a c #

Category c => Category (IQ c :: k -> k -> Type) Source # 
Instance details

Defined in Data.Quiver

Methods

id :: IQ c a a #

(.) :: IQ c b c0 -> IQ c a b -> IQ c a c0 #

Category c => Category (OpQ c :: k -> k -> Type) Source # 
Instance details

Defined in Data.Quiver

Methods

id :: OpQ c a a #

(.) :: OpQ c b c0 -> OpQ c a b -> OpQ c a c0 #

Monoid m => Category (KQ m :: k -> k -> Type) Source # 
Instance details

Defined in Data.Quiver

Methods

id :: KQ m a a #

(.) :: KQ m b c -> KQ m a b -> KQ m a c #

(Category p, Category q) => Category (ProductQ p q :: k -> k -> Type) Source # 
Instance details

Defined in Data.Quiver

Methods

id :: ProductQ p q a a #

(.) :: ProductQ p q b c -> ProductQ p q a b -> ProductQ p q a c #

(Applicative m, Category c) => Category (ApQ m c :: k -> k -> Type) Source # 
Instance details

Defined in Data.Quiver

Methods

id :: ApQ m c a a #

(.) :: ApQ m c b c0 -> ApQ m c a b -> ApQ m c a c0 #

(Category p, p ~ q) => Category (ComposeQ p q :: k -> k -> Type) Source # 
Instance details

Defined in Data.Quiver

Methods

id :: ComposeQ p q a a #

(.) :: ComposeQ p q b c -> ComposeQ p q a b -> ComposeQ p q a c #

p ~ q => Category (LeftQ p q :: k2 -> k2 -> Type) Source # 
Instance details

Defined in Data.Quiver

Methods

id :: LeftQ p q a a #

(.) :: LeftQ p q b c -> LeftQ p q a b -> LeftQ p q a c #

p ~ q => Category (RightQ p q :: k1 -> k1 -> Type) Source # 
Instance details

Defined in Data.Quiver

Methods

id :: RightQ p q a a #

(.) :: RightQ p q b c -> RightQ p q a b -> RightQ p q a c #

Category ((->) :: Type -> Type -> Type)

Since: base-3.0

Instance details

Defined in Control.Category

Methods

id :: a -> a #

(.) :: (b -> c) -> (a -> b) -> a -> c #