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

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 -> *) (a :: k) (b :: k) = Op {
- runOp :: f b a
}
data ListTr :: (k -> k -> *) -> k -> k -> * where
- NilTr :: ListTr f a a
- ConsTr :: f b c -> ListTr f a b -> ListTr f a c
data Queue (f :: k -> k -> *) (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
emptyQ :: Queue (f :: k -> k -> *) a a
cons :: forall (f :: k -> k -> *) a b c. f b c -> Queue f a b -> Queue f a c
uncons :: Queue f a b -> ViewL f a b
snoc :: forall (f :: k -> k -> *) a b c. Queue f b c -> f a b -> Queue f a c
foldQ :: 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
zipWithQ :: forall f g a b a' b'. Arrow 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 -> *) (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

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

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

Free category encoded as a recursive data type, in a simlar way as Free. You can use FreeAlgebra2 class instance:

liftFree2    @Cat :: f a b -> Cat f ab

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

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

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) Source #
Instance details 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) Source #
Instance details 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) 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 #
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

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

Type alligned real time queues; Based on `Purely Functinal Data Structures` C.Okasaki.

Upper bounds of cons, snoc, uncons are O(1) (worst case).

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

emptyQ :: Queue (f :: k -> k -> *) a a Source #

cons :: forall (f :: k -> k -> *) a b c. f b c -> Queue f a b -> Queue f a c Source #

uncons :: Queue f a b -> ViewL f a b Source #

uncons a Queue, complexity: O(1)

snoc :: forall (f :: k -> k -> *) a b c. Queue f b c -> f a b -> Queue f a c Source #

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

Efficient fold of a queue into a category.

complexity O(n)

zipWithQ :: forall f g a b a' b'. Arrow 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 #