Copyright	(c) Eitan Chatav 2019
Maintainer	eitan@morphism.tech
Stability	experimental
Safe Haskell	Safe
Language	Haskell2010

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

data Path p x y where
- Done :: Path p x x
- (:>>) :: p x y -> Path p y z -> Path p x z
pattern (:<<) :: Path p y z -> p x y -> Path p x z
newtype FoldPath p x y = FoldPath {
- getFoldPath :: forall q. Category q => (forall x y. p x y -> q x y) -> q x y
}
class (QPointed c, QFoldable c, forall p. Category (c p)) => CFree c
toPath :: (QFoldable c, CFree path) => c p x y -> path p x y
reversePath :: (QFoldable c, CFree path) => c p x y -> path (OpQ p) y x
beforeAll :: (QFoldable c, CFree path) => (forall x. p x x) -> c p x y -> path p x y
afterAll :: (QFoldable c, CFree path) => (forall x. p x x) -> c p x y -> path p x y
class Category (cat :: k -> k -> Type) where
- id :: cat a a
- (.) :: cat b c -> cat a b -> cat a c

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 getFoldPath :: forall q. Category q => (forall x y. p x y -> q x y) -> q x y

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 #