free-category-0.0.4.4: efficient data types for free categories and arrows
Safe HaskellSafe-Inferred
LanguageHaskell2010
Extensions
  • Cpp
  • MonoLocalBinds
  • ScopedTypeVariables
  • TypeFamilies
  • ViewPatterns
  • GADTs
  • GADTSyntax
  • PolyKinds
  • TypeSynonymInstances
  • FlexibleInstances
  • KindSignatures
  • RankNTypes
  • TypeOperators
  • 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

Documentation

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

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

Constructors

Op 

Fields

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 #

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 #

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 #

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 #

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

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 #

ArrowZero f => ArrowZero (ListTr f) Source # 
Instance details

Defined in Control.Category.Free.Internal

Methods

zeroArrow :: ListTr f b c #

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 #

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 #

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

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 :: (k1 -> k1 -> Type) -> k1 -> k1 -> Type) (c :: k2 -> k2 -> Type) Source # 
Instance details

Defined in Control.Category.Free.Internal

type AlgebraType (ListTr :: (k1 -> k1 -> Type) -> k1 -> k1 -> Type) (c :: k2 -> k2 -> 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 #

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 #

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 aligned real time queues; Based on `Purely Functional 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') #

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 #

ArrowZero f => ArrowZero (Queue f) Source # 
Instance details

Defined in Control.Category.Free.Internal

Methods

zeroArrow :: Queue f b c #

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 #

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 #

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

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 :: (k1 -> k1 -> Type) -> k1 -> k1 -> Type) (c :: k2 -> k2 -> Type) Source # 
Instance details

Defined in Control.Category.Free.Internal

type AlgebraType (Queue :: (k1 -> k1 -> Type) -> k1 -> k1 -> Type) (c :: k2 -> k2 -> 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 #

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 #