Safe Haskell	None
Language	Haskell2010
Extensions	Cpp MonoLocalBinds ScopedTypeVariables TypeFamilies ViewPatterns GADTs GADTSyntax PolyKinds TypeSynonymInstances FlexibleInstances KindSignatures RankNTypes ExplicitNamespaces ExplicitForAll PatternSynonyms QuantifiedConstraints

Control.Category.Free.Internal

Description

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

Synopsis

newtype Op (f :: k -> k -> Type) (a :: k) (b :: k) = Op {
- runOp :: f b a
}
hoistOp :: forall k (f :: k -> k -> Type) (g :: k -> k -> Type) a b. (forall x y. f x y -> g x y) -> Op f a b -> Op g a b
data ListTr :: (k -> k -> Type) -> k -> k -> Type where
- NilTr :: ListTr f a a
- ConsTr :: f b c -> ListTr f a b -> ListTr f a c
liftL :: forall k (f :: k -> k -> Type) x y. f x y -> ListTr f x y
foldNatL :: forall k (f :: k -> k -> Type) 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 k (f :: k -> k -> Type) 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
foldlL :: forall k (f :: k -> k -> Type) 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
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 -> Type) (a :: k) (b :: k) where
- pattern NilQ :: () => a ~ b => Queue f a b
- pattern ConsQ :: f b c -> Queue f a b -> Queue f a c
liftQ :: forall k (f :: k -> k -> Type) a b. f a b -> Queue f a b
nilQ :: Queue (f :: k -> k -> Type) a a
consQ :: forall k (f :: k -> k -> Type) a b c. f b c -> Queue f a b -> Queue f a c
data ViewL f a b where
- 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
snocQ :: forall k (f :: k -> k -> Type) a b c. Queue f b c -> f a b -> Queue f a c
foldNatQ :: forall k (f :: k -> k -> Type) c a b. Category c => (forall x y. f x y -> c x y) -> Queue f a b -> c a b
foldrQ :: forall k (f :: k -> k -> Type) 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
foldlQ :: forall k (f :: k -> k -> Type) 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
hoistQ :: forall k (f :: k -> k -> Type) (g :: k -> k -> Type) a b. (forall x y. f x y -> g x y) -> Queue f a b -> Queue g 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')

Documentation

newtype Op (f :: k -> k -> Type) (a :: k) (b :: k) Source #

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

Instances details

Category f => Category (Op f :: k -> k -> Type) Source #
Instance details Defined in Control.Category.Free.Internal Methods id :: forall (a :: k0). Op f a a # (.) :: forall (b :: k0) (c :: k0) (a :: k0). Op f b c -> Op f a b -> Op f a c #
Show (f b a) => Show (Op f a b) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details 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 k (f :: k -> k -> Type) (g :: k -> k -> Type) a b. (forall x y. f x y -> g x y) -> Op f a b -> Op g a b Source #

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

data ListTr :: (k -> k -> Type) -> k -> k -> Type where Source #

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

Instances details

FreeAlgebra2 (ListTr :: (k -> k -> Type) -> k -> k -> Type) Source #
Instance details Defined in Control.Category.Free.Internal Methods liftFree2 :: forall f (a :: k0) (b :: k0). AlgebraType0 ListTr f => f a b -> ListTr f a b # foldNatFree2 :: forall d f (a :: k0) (b :: k0). (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 :: forall (f :: k0 -> k0 -> Type). AlgebraType0 ListTr f => Proof (AlgebraType ListTr (ListTr f)) (ListTr f) # forget2 :: forall (f :: k0 -> k0 -> Type). AlgebraType ListTr f => Proof (AlgebraType0 ListTr f) (ListTr f) #
Category (ListTr f :: k -> k -> Type) Source #
Instance details Defined in Control.Category.Free.Internal Methods id :: forall (a :: k0). ListTr f a a # (.) :: forall (b :: k0) (c :: k0) (a :: k0). ListTr f b c -> ListTr f a b -> ListTr f a c #
Arrow f => Arrow (ListTr f) Source #
Instance details 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) Source #
Instance details Defined in Control.Category.Free.Internal Methods zeroArrow :: ListTr f b c #
ArrowChoice f => ArrowChoice (ListTr f) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details Defined in Control.Category.Free.Internal type AlgebraType (ListTr :: (k2 -> k2 -> Type) -> k2 -> k2 -> Type) (c :: k1 -> k1 -> Type) = Category c

liftL :: forall k (f :: k -> k -> Type) x y. f x y -> ListTr f x y Source #

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

lengthListTr :: ListTr f a b -> Int Source #

foldrL :: forall k (f :: k -> k -> Type) 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 Source #

foldr of a ListTr

foldlL :: forall k (f :: k -> k -> Type) 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 Source #

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') Source #

data Queue (f :: k -> k -> Type) (a :: k) (b :: k) where Source #

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

Instances details

FreeAlgebra2 (Queue :: (k -> k -> Type) -> k -> k -> Type) Source #
Instance details Defined in Control.Category.Free.Internal Methods liftFree2 :: forall f (a :: k0) (b :: k0). AlgebraType0 Queue f => f a b -> Queue f a b # foldNatFree2 :: forall d f (a :: k0) (b :: k0). (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 :: forall (f :: k0 -> k0 -> Type). AlgebraType0 Queue f => Proof (AlgebraType Queue (Queue f)) (Queue f) # forget2 :: forall (f :: k0 -> k0 -> Type). AlgebraType Queue f => Proof (AlgebraType0 Queue f) (Queue f) #
Category (Queue f :: k -> k -> Type) Source #
Instance details Defined in Control.Category.Free.Internal Methods id :: forall (a :: k0). Queue f a a # (.) :: forall (b :: k0) (c :: k0) (a :: k0). Queue f b c -> Queue f a b -> Queue f a c #
Arrow f => Arrow (Queue f) Source #
Instance details 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) Source #
Instance details Defined in Control.Category.Free.Internal Methods zeroArrow :: Queue f b c #
ArrowChoice f => ArrowChoice (Queue f) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details Defined in Control.Category.Free.Internal type AlgebraType (Queue :: (k2 -> k2 -> Type) -> k2 -> k2 -> Type) (c :: k1 -> k1 -> Type) = Category c

liftQ :: forall k (f :: k -> k -> Type) a b. f a b -> Queue f a b Source #

nilQ :: Queue (f :: k -> k -> Type) a a Source #

consQ :: forall k (f :: k -> k -> Type) a b c. f b c -> Queue f a b -> Queue f a c Source #

data ViewL f a b where Source #

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 Source #

uncons a Queue, complexity: O(1)

snocQ :: forall k (f :: k -> k -> Type) a b c. Queue f b c -> f a b -> Queue f a c Source #

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

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

complexity O(n)

foldrQ :: forall k (f :: k -> k -> Type) 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 Source #

foldr of a Queue

foldlQ :: forall k (f :: k -> k -> Type) 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 Source #

foldl of a Queue

TODO: make it strict, like foldl'.

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

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') Source #