Control.Category.Free

Consider the category of Haskell "quivers" with

• objects are types of higher kind

• p :: k -> k -> Type

• morphisms are terms of RankNType,

• forall x y. p x y -> q x y

• identity is id
• composition is .

Now, consider the subcategory of Haskell Categorys with

• constrained objects Category c => c
• morphisms act functorially

• t :: (Category c, Category d) => c x y -> d x y

• t id = id

• t (g . f) = t g . t f

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
  cfold path "hello"
:}
25

Constructors

Done :: Path p x x

(:>>) :: p x y -> Path p y z -> Path p x z infixr 7

Instances

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

Defined in Control.Category.Free

Methods

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

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

Defined in Control.Category.Free

Methods

csingleton :: p x y -> Path p x y

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

Defined in Control.Category.Free

Methods

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

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

Defined in Control.Category.Free

Methods

cfoldMap :: Category q => (forall (x :: k0) (y :: k0). p x y -> q x y) -> Path p x y -> q x y

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

cfoldr :: (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

cfoldl :: (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

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

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

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

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 cfoldMap function.

Constructors

FoldPath

Fields

• getFoldPath :: forall q. Category q => (forall x y. p x y -> q x y) -> q x y

Instances

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

Defined in Control.Category.Free

Methods

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

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

Defined in Control.Category.Free

Methods

csingleton :: p x y -> FoldPath p x y

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

Defined in Control.Category.Free

Methods

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

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

Defined in Control.Category.Free

Methods

cfoldMap :: Category q => (forall (x :: k0) (y :: k0). p x y -> q x y) -> FoldPath p x y -> q x y

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

cfoldr :: (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

cfoldl :: (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

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

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

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

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 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 (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 ((:~~:) :: k -> k -> Type)

Since: base-4.10.0.0

Defined in Control.Category

Methods

id :: a :~~: a

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

Category (EndoR p :: k1 -> k1 -> Type)

Defined in Control.Category.Free

Methods

id :: EndoR p a a

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

Category (EndoL p :: k2 -> k2 -> Type)

Defined in Control.Category.Free

Methods

id :: EndoL p a a

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

Monoid m => Category (MCat m :: k -> k -> Type)

Defined in Control.Category.Free

Methods

id :: MCat m a a

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

(Applicative m, Category c) => Category (ApCat m c :: k -> k -> Type)

Defined in Control.Category.Free

Methods

id :: ApCat m c a a

(.) :: ApCat m c b c0 -> ApCat m c a b -> ApCat m c a c0

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

Since: base-3.0

Defined in Control.Category

Methods

id :: a -> a

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

class (forall p. Category (c p)) => CFunctor c where

A functor from quivers to Categorys.

cmap _ id = id

cmap f (c >>> c') = f c >>> f c'

Methods

cmap :: (forall x y. p x y -> q x y) -> c p x y -> c q x y

Instances

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

Defined in Control.Category.Free

Methods

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

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

Defined in Control.Category.Free

Methods

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

class CFunctor c => CFoldable c where

Generalizing Foldable from Monoids to Categorys.

cmap f = cfoldMap (csingleton . f)

Minimal complete definition

cfoldMap

Methods

cfoldMap :: Category q => (forall x y. p x y -> q x y) -> c p x y -> q x y

Map each element of the structure to a Category, and combine the results.

cfold :: Category q => c q x y -> q x y

Combine the elements of a structure using a Category.

cfoldr :: (forall x y z. p x y -> q y z -> q x z) -> q y z -> c p x y -> q x z

Right-associative fold of a structure.

In the case of Paths, cfoldr, when applied to a binary operator, a starting value, and a Path, reduces the Path using the binary operator, from right to left:

cfoldr (?) q (p1 :>> p2 :>> ... :>> pn :>> Done) == p1 ? (p2 ? ... (pn ? q) ...)

cfoldl :: (forall x y z. q x y -> p y z -> q x z) -> q x y -> c p y z -> q x z

Left-associative fold of a structure.

In the case of Paths, cfoldl, when applied to a binary operator, a starting value, and a Path, reduces the Path using the binary operator, from left to right:

cfoldl (?) q (p1 :>> p2 :>> ... :>> pn :>> Done) == (... ((q ? p1) ? p2) ? ...) ? pn

ctoMonoid :: Monoid m => (forall x y. p x y -> m) -> c p x y -> m

Map each element of the structure to a Monoid, and combine the results.

ctoList :: (forall x y. p x y -> a) -> c p x y -> [a]

Map each element of the structure, and combine the results in a list.

ctraverse_ :: (Applicative m, Category q) => (forall x y. p x y -> m (q x y)) -> c p x y -> m (q x y)

Map each element of a structure to an Applicative on a Category, evaluate from left to right, and combine the results.

Instances

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

Defined in Control.Category.Free

Methods

cfoldMap :: Category q => (forall (x :: k0) (y :: k0). p x y -> q x y) -> FoldPath p x y -> q x y

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

cfoldr :: (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

cfoldl :: (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

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

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

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

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

Defined in Control.Category.Free

Methods

cfoldMap :: Category q => (forall (x :: k0) (y :: k0). p x y -> q x y) -> Path p x y -> q x y

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

cfoldr :: (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

cfoldl :: (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

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

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

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

class CFoldable c => CTraversable c where

Generalizing Traversable to Categorys.

Methods

ctraverse :: Applicative m => (forall x y. p x y -> m (q x y)) -> c p x y -> m (c q x y)

Map each element of a structure to an Applicative on a quiver, evaluate from left to right, and collect the results.

Instances

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

Defined in Control.Category.Free

Methods

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

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

Defined in Control.Category.Free

Methods

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

class CTraversable c => CFree c where

Unpacking the definition of a left adjoint to the forgetful functor from Categorys to quivers, there must be a function csingleton, such that any function

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

factors uniquely through c p x y as

cfoldMap f . csingleton = f

Methods

csingleton :: p x y -> c p x y

Instances

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

Defined in Control.Category.Free

Methods

csingleton :: p x y -> FoldPath p x y

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

Defined in Control.Category.Free

Methods

csingleton :: p x y -> Path p x y

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

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

newtype EndoL p x y

Used in the default definition of cfoldr.

Constructors

EndoL

Fields

• getEndoL :: forall w. p w x -> p w y

Instances

Category (EndoL p :: k2 -> k2 -> Type)

Defined in Control.Category.Free

Methods

id :: EndoL p a a

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

newtype EndoR p y x

Used in the default definition of cfoldr.

Constructors

EndoR

Fields

• getEndoR :: forall z. p x z -> p y z

Instances

Category (EndoR p :: k1 -> k1 -> Type)

Defined in Control.Category.Free

Methods

id :: EndoR p a a

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

newtype MCat m x y

Turn a Monoid into a Category, used in the default definition of ctoMonoid.

Constructors

MCat

Fields

• getMCat :: m

Instances

Monoid m => Category (MCat m :: k -> k -> Type)

Defined in Control.Category.Free

Methods

id :: MCat m a a

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

Eq m => Eq (MCat m x y)

Defined in Control.Category.Free

Methods

(==) :: MCat m x y -> MCat m x y -> Bool

(/=) :: MCat m x y -> MCat m x y -> Bool

Ord m => Ord (MCat m x y)

Defined in Control.Category.Free

Methods

compare :: MCat m x y -> MCat m x y -> Ordering

(<) :: MCat m x y -> MCat m x y -> Bool

(<=) :: MCat m x y -> MCat m x y -> Bool

(>) :: MCat m x y -> MCat m x y -> Bool

(>=) :: MCat m x y -> MCat m x y -> Bool

max :: MCat m x y -> MCat m x y -> MCat m x y

min :: MCat m x y -> MCat m x y -> MCat m x y

Show m => Show (MCat m x y)

Defined in Control.Category.Free

Methods

showsPrec :: Int -> MCat m x y -> ShowS

show :: MCat m x y -> String

showList :: [MCat m x y] -> ShowS

newtype ApCat m c x y

Turn an Applicative over a Category into a Category, used in the default definition of ctraverse_.

Constructors

ApCat

Fields

• getApCat :: m (c x y)

Instances

(Applicative m, Category c) => Category (ApCat m c :: k -> k -> Type)

Defined in Control.Category.Free

Methods

id :: ApCat m c a a

(.) :: ApCat m c b c0 -> ApCat m c a b -> ApCat m c a c0

Eq (m (c x y)) => Eq (ApCat m c x y)

Defined in Control.Category.Free

Methods

(==) :: ApCat m c x y -> ApCat m c x y -> Bool

(/=) :: ApCat m c x y -> ApCat m c x y -> Bool

Ord (m (c x y)) => Ord (ApCat m c x y)

Defined in Control.Category.Free

Methods

compare :: ApCat m c x y -> ApCat m c x y -> Ordering

(<) :: ApCat m c x y -> ApCat m c x y -> Bool

(<=) :: ApCat m c x y -> ApCat m c x y -> Bool

(>) :: ApCat m c x y -> ApCat m c x y -> Bool

(>=) :: ApCat m c x y -> ApCat m c x y -> Bool

max :: ApCat m c x y -> ApCat m c x y -> ApCat m c x y

min :: ApCat m c x y -> ApCat m c x y -> ApCat m c x y

Show (m (c x y)) => Show (ApCat m c x y)

Defined in Control.Category.Free

Methods

showsPrec :: Int -> ApCat m c x y -> ShowS

show :: ApCat m c x y -> String

showList :: [ApCat m c x y] -> ShowS