Control.Category.Free.Internal

Internal module, contains implementation of type aligned real time queues (C.Okasaki 'Purely Functional Data Structures').

Documentation

newtype Op (f :: k -> k -> *) (a :: k) (b :: k)

Oposite categoy in which arrows from a to b are represented by arrows from b to a in the original category.

Constructors

Op

Fields

• runOp :: f b a

Instances

Category f => Category (Op f :: k -> k -> Type)

Defined in Control.Category.Free.Internal

Methods

id :: Op f a a

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

Show (f b a) => Show (Op f a b)

Defined in Control.Category.Free.Internal

Methods

showsPrec :: Int -> Op f a b -> ShowS

show :: Op f a b -> String

showList :: [Op f a b] -> ShowS

Category f => Semigroup (Op f o o)

Defined in Control.Category.Free.Internal

Methods

(<>) :: Op f o o -> Op f o o -> Op f o o

sconcat :: NonEmpty (Op f o o) -> Op f o o

stimes :: Integral b => b -> Op f o o -> Op f o o

Category f => Monoid (Op f o o)

Defined in Control.Category.Free.Internal

Methods

mempty :: Op f o o

mappend :: Op f o o -> Op f o o -> Op f o o

mconcat :: [Op f o o] -> Op f o o

hoistOp :: forall (f :: k -> k -> *) (g :: k -> k -> *) a b. (forall x y. f x y -> g x y) -> Op f a b -> Op g a b

Op is an endo-functor of the category of categories.

data ListTr :: (k -> k -> *) -> k -> k -> * where

Simple representation of a free category by using type aligned lists. This is not a surprise as free monoids can be represented by lists (up to laziness)

ListTr has FreeAlgebra2 class instance:

liftFree2    @ListTr :: f a b -> ListTr f ab
foldNatFree2 @ListTr :: Category d
                     => (forall x y. f x y -> d x y)
                     -> ListTr f a b
                     -> d a b

The same performance concerns that apply to Free apply to this encoding of a free category.

Note that even though this is a naive version, it behaves quite well in simple benchmarks and quite stable regardless of the level of optimisations.

Constructors

NilTr :: ListTr f a a

ConsTr :: f b c -> ListTr f a b -> ListTr f a c

Instances

FreeAlgebra2 (ListTr :: (k -> k -> Type) -> k -> k -> Type)

Defined in Control.Category.Free.Internal

Methods

liftFree2 :: AlgebraType0 ListTr f => f a b -> ListTr f a b

foldNatFree2 :: (AlgebraType ListTr d, AlgebraType0 ListTr f) => (forall (x :: k0) (y :: k0). f x y -> d x y) -> ListTr f a b -> d a b

codom2 :: AlgebraType0 ListTr f => Proof (AlgebraType ListTr (ListTr f)) (ListTr f)

forget2 :: AlgebraType ListTr f => Proof (AlgebraType0 ListTr f) (ListTr f)

Category (ListTr f :: k -> k -> Type)

Defined in Control.Category.Free.Internal

Methods

id :: ListTr f a a

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

Arrow f => Arrow (ListTr f)

Defined in Control.Category.Free.Internal

Methods

arr :: (b -> c) -> ListTr f b c

first :: ListTr f b c -> ListTr f (b, d) (c, d)

second :: ListTr f b c -> ListTr f (d, b) (d, c)

(***) :: ListTr f b c -> ListTr f b' c' -> ListTr f (b, b') (c, c')

(&&&) :: ListTr f b c -> ListTr f b c' -> ListTr f b (c, c')

ArrowZero f => ArrowZero (ListTr f)

Defined in Control.Category.Free.Internal

Methods

zeroArrow :: ListTr f b c

ArrowChoice f => ArrowChoice (ListTr f)

Defined in Control.Category.Free.Internal

Methods

left :: ListTr f b c -> ListTr f (Either b d) (Either c d)

right :: ListTr f b c -> ListTr f (Either d b) (Either d c)

(+++) :: ListTr f b c -> ListTr f b' c' -> ListTr f (Either b b') (Either c c')

(|||) :: ListTr f b d -> ListTr f c d -> ListTr f (Either b c) d

(forall (x :: k) (y :: k). Show (f x y)) => Show (ListTr f a b)

Defined in Control.Category.Free.Internal

Methods

showsPrec :: Int -> ListTr f a b -> ShowS

show :: ListTr f a b -> String

showList :: [ListTr f a b] -> ShowS

Semigroup (ListTr f o o)

Defined in Control.Category.Free.Internal

Methods

(<>) :: ListTr f o o -> ListTr f o o -> ListTr f o o

sconcat :: NonEmpty (ListTr f o o) -> ListTr f o o

stimes :: Integral b => b -> ListTr f o o -> ListTr f o o

Monoid (ListTr f o o)

Defined in Control.Category.Free.Internal

Methods

mempty :: ListTr f o o

mappend :: ListTr f o o -> ListTr f o o -> ListTr f o o

mconcat :: [ListTr f o o] -> ListTr f o o

type AlgebraType0 (ListTr :: (k -> k -> Type) -> k -> k -> Type) (f :: l)

Defined in Control.Category.Free.Internal

type AlgebraType0 (ListTr :: (k -> k -> Type) -> k -> k -> Type) (f :: l) = ()

type AlgebraType (ListTr :: (k2 -> k2 -> Type) -> k2 -> k2 -> Type) (c :: k1 -> k1 -> Type)

Defined in Control.Category.Free.Internal

type AlgebraType (ListTr :: (k2 -> k2 -> Type) -> k2 -> k2 -> Type) (c :: k1 -> k1 -> Type) = Category c

liftL :: forall (f :: k -> k -> *) x y. f x y -> ListTr f x y

foldNatL :: forall (f :: k -> k -> *) c a b. Category c => (forall x y. f x y -> c x y) -> ListTr f a b -> c a b

lengthListTr :: ListTr f a b -> Int

foldrL :: forall (f :: k -> k -> *) c a b d. (forall x y z. f y z -> c x y -> c x z) -> c a b -> ListTr f b d -> c a d

foldr of a ListTr

foldlL :: forall (f :: k -> k -> *) c a b d. (forall x y z. c y z -> f x y -> c x z) -> c b d -> ListTr f a b -> c a d

foldl of a ListTr

TODO: make it strict, like foldl'.

zipWithL :: forall f g a b a' b'. Category f => (forall x y x' y'. f x y -> f x' y' -> f (g x x') (g y y')) -> ListTr f a b -> ListTr f a' b' -> ListTr f (g a a') (g b b')

data Queue (f :: k -> k -> *) (a :: k) (b :: k) where

Type alligned real time queues; Based on `Purely Functinal Data Structures` C.Okasaki. This the most reliably behaved implementation of free categories in this package.

Upper bounds of consQ, snocQ, unconsQ are O(1) (worst case).

Internal invariant: sum of lengths of two last least is equal the length of the first one.

Bundled Patterns

pattern NilQ :: () => a ~ b => Queue f a b

pattern ConsQ :: f b c -> Queue f a b -> Queue f a c

Instances

FreeAlgebra2 (Queue :: (k -> k -> Type) -> k -> k -> Type)

Defined in Control.Category.Free.Internal

Methods

liftFree2 :: AlgebraType0 Queue f => f a b -> Queue f a b

foldNatFree2 :: (AlgebraType Queue d, AlgebraType0 Queue f) => (forall (x :: k0) (y :: k0). f x y -> d x y) -> Queue f a b -> d a b

codom2 :: AlgebraType0 Queue f => Proof (AlgebraType Queue (Queue f)) (Queue f)

forget2 :: AlgebraType Queue f => Proof (AlgebraType0 Queue f) (Queue f)

Category (Queue f :: k -> k -> Type)

Defined in Control.Category.Free.Internal

Methods

id :: Queue f a a

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

Arrow f => Arrow (Queue f)

Defined in Control.Category.Free.Internal

Methods

arr :: (b -> c) -> Queue f b c

first :: Queue f b c -> Queue f (b, d) (c, d)

second :: Queue f b c -> Queue f (d, b) (d, c)

(***) :: Queue f b c -> Queue f b' c' -> Queue f (b, b') (c, c')

(&&&) :: Queue f b c -> Queue f b c' -> Queue f b (c, c')

ArrowZero f => ArrowZero (Queue f)

Defined in Control.Category.Free.Internal

Methods

zeroArrow :: Queue f b c

ArrowChoice f => ArrowChoice (Queue f)

Defined in Control.Category.Free.Internal

Methods

left :: Queue f b c -> Queue f (Either b d) (Either c d)

right :: Queue f b c -> Queue f (Either d b) (Either d c)

(+++) :: Queue f b c -> Queue f b' c' -> Queue f (Either b b') (Either c c')

(|||) :: Queue f b d -> Queue f c d -> Queue f (Either b c) d

(forall (x :: k) (y :: k). Show (f x y)) => Show (Queue f a b)

Defined in Control.Category.Free.Internal

Methods

showsPrec :: Int -> Queue f a b -> ShowS

show :: Queue f a b -> String

showList :: [Queue f a b] -> ShowS

Semigroup (Queue f o o)

Defined in Control.Category.Free.Internal

Methods

(<>) :: Queue f o o -> Queue f o o -> Queue f o o

sconcat :: NonEmpty (Queue f o o) -> Queue f o o

stimes :: Integral b => b -> Queue f o o -> Queue f o o

Monoid (Queue f o o)

Defined in Control.Category.Free.Internal

Methods

mempty :: Queue f o o

mappend :: Queue f o o -> Queue f o o -> Queue f o o

mconcat :: [Queue f o o] -> Queue f o o

type AlgebraType0 (Queue :: (k -> k -> Type) -> k -> k -> Type) (f :: l)

Defined in Control.Category.Free.Internal

type AlgebraType0 (Queue :: (k -> k -> Type) -> k -> k -> Type) (f :: l) = ()

type AlgebraType (Queue :: (k2 -> k2 -> Type) -> k2 -> k2 -> Type) (c :: k1 -> k1 -> Type)

Defined in Control.Category.Free.Internal

type AlgebraType (Queue :: (k2 -> k2 -> Type) -> k2 -> k2 -> Type) (c :: k1 -> k1 -> Type) = Category c

liftQ :: forall (f :: k -> k -> *) a b. f a b -> Queue f a b

nilQ :: Queue (f :: k -> k -> *) a a

consQ :: forall (f :: k -> k -> *) a b c. f b c -> Queue f a b -> Queue f a c

data ViewL f a b where

Constructors

EmptyL :: ViewL f a a

(:<) :: f b c -> Queue f a b -> ViewL f a c

unconsQ :: Queue f a b -> ViewL f a b

uncons a Queue, complexity: O(1)

snocQ :: forall (f :: k -> k -> *) a b c. Queue f b c -> f a b -> Queue f a c

foldNatQ :: forall (f :: k -> k -> *) c a b. Category c => (forall x y. f x y -> c x y) -> Queue f a b -> c a b

Efficient fold of a queue into a category, analogous to foldM.

complexity O(n)

foldrQ :: forall (f :: k -> k -> *) c a b d. (forall x y z. f y z -> c x y -> c x z) -> c a b -> Queue f b d -> c a d

foldr of a Queue

foldlQ :: forall (f :: k -> k -> *) c a b d. (forall x y z. c y z -> f x y -> c x z) -> c b d -> Queue f a b -> c a d

foldl of a Queue

TODO: make it strict, like foldl'.

hoistQ :: forall (f :: k -> k -> *) (g :: k -> k -> *) a b. (forall x y. f x y -> g x y) -> Queue f a b -> Queue g a b

Queue is an endo-functor on the category of graphs (or category of categories), thus one can hoist the transitions using a natural transformation. This in analogy to map :: (a -> b) -> [a] -> [b].

zipWithQ :: forall f g a b a' b'. Category f => (forall x y x' y'. f x y -> f x' y' -> f (g x x') (g y y')) -> Queue f a b -> Queue f a' b' -> Queue f (g a a') (g b b')