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

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

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

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)

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

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

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

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

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

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

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

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