Control.Category.Free

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

Documentation

data Path p x y where

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)

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

QMonad (Path :: (k -> k -> Type) -> k -> k -> Type)

Defined in Control.Category.Free

Methods

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

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

QPointed (Path :: (k -> k -> Type) -> k -> k -> Type)

Defined in Control.Category.Free

Methods

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

QTraversable (Path :: (k -> k -> Type) -> k -> k -> Type)

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)

QFoldable (Path :: (k -> k -> Type) -> k -> k -> Type)

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

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

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

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

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

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

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)

CFree (Path :: (k -> k -> Type) -> k -> k -> Type)

Defined in Control.Category.Free

Category (Path p :: k -> k -> Type)

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)

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)

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)

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

The snoc pattern for right-to-left composition.

newtype FoldPath p x y

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)

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

QMonad (FoldPath :: (k -> k -> Type) -> k -> k -> Type)

Defined in Control.Category.Free

Methods

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

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

QPointed (FoldPath :: (k -> k -> Type) -> k -> k -> Type)

Defined in Control.Category.Free

Methods

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

QTraversable (FoldPath :: (k -> k -> Type) -> k -> k -> Type)

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)

QFoldable (FoldPath :: (k -> k -> Type) -> k -> k -> Type)

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

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

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

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

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

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

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)

CFree (FoldPath :: (k -> k -> Type) -> k -> k -> Type)

Defined in Control.Category.Free

Category (FoldPath p :: k -> k -> Type)

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)

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)

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

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)

Defined in Control.Category.Free

CFree (Path :: (k -> k -> Type) -> k -> k -> Type)

Defined in Control.Category.Free

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

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

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

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

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

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

Defined in Control.Category

Methods

id :: a :~: a

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

Category c => Category (IsoQ c :: k -> k -> Type)

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)

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

Defined in Control.Category

Methods

id :: a :~~: a

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

Category (Path p :: k -> k -> Type)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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

Defined in Control.Category

Methods

id :: a -> a

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