cartesian-profunctors
Safe HaskellNone
LanguageHaskell2010

Data.Finitary.PolyRep

Description

A normalized polynomial representation for finitary polynomial functors.

Compared with Data.Finitary.TreeRep, this module forgets the syntactic tree structure of sums and products and represents a functor as

x^n1 + x^n2 + ... + x^nk

This is especially useful for Day convolution: monomials satisfy

Day x^m x^n ≅ x^(m*n)

which is implemented by DayPoly, fromDay, and toDay.

The list order in Poly is operationally significant in Haskell, but mathematically it should be regarded as a chosen ordering of summands.

Synopsis

Base Type and its algebra

type Poly = [Nat] Source #

Finitary polynomial f(x) = x^e1 + x^e2 + ... + x^en represented as a list of exponents [e1, e2, ..., en]

zeroPoly :: Poly Source #

addPoly :: Poly -> Poly -> Poly Source #

onePoly :: Poly Source #

multPoly :: Poly -> Poly -> Poly Source #

parPoly :: Poly Source #

Type-level Poly algebra

type AddPoly (r1 :: Poly) (r2 :: Poly) = r1 ++ r2 Source #

type family MultPoly (r1 :: Poly) (r2 :: Poly) :: Poly where ... Source #

Equations

MultPoly ('[] :: [Nat]) _1 = '[] :: [Nat] 
MultPoly (e ': es) r2 = AddPoly (MultPoly1 e r2) (MultPoly es r2) 

type family DayPoly (r1 :: Poly) (r2 :: Poly) :: Poly where ... Source #

Equations

DayPoly ('[] :: [Nat]) _1 = '[] :: [Nat] 
DayPoly (e ': es) r2 = AddPoly (DayPoly1 e r2) (DayPoly es r2) 

data SPoly (r :: Poly) where Source #

Constructors

SNil :: SPoly ('[] :: [Nat]) 
SCons :: forall (e :: Nat) (es :: [Nat]). !(SNat e) -> !(SPoly es) -> SPoly (e ': es) 

Instances

Instances details
TestEquality SPoly Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

testEquality :: forall (a :: Poly) (b :: Poly). SPoly a -> SPoly b -> Maybe (a :~: b) #

Show (SPoly r) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

showsPrec :: Int -> SPoly r -> ShowS #

show :: SPoly r -> String #

showList :: [SPoly r] -> ShowS #

Eq (SPoly r) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

(==) :: SPoly r -> SPoly r -> Bool #

(/=) :: SPoly r -> SPoly r -> Bool #

Ord (SPoly r) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

compare :: SPoly r -> SPoly r -> Ordering #

(<) :: SPoly r -> SPoly r -> Bool #

(<=) :: SPoly r -> SPoly r -> Bool #

(>) :: SPoly r -> SPoly r -> Bool #

(>=) :: SPoly r -> SPoly r -> Bool #

max :: SPoly r -> SPoly r -> SPoly r #

min :: SPoly r -> SPoly r -> SPoly r #

sAddPoly :: forall (r1 :: Poly) (r2 :: Poly). SPoly r1 -> SPoly r2 -> SPoly (AddPoly r1 r2) Source #

(%++) :: forall (r1 :: Poly) (r2 :: Poly). SPoly r1 -> SPoly r2 -> SPoly (AddPoly r1 r2) Source #

sMultPoly :: forall (r1 :: Poly) (r2 :: Poly). SPoly r1 -> SPoly r2 -> SPoly (MultPoly r1 r2) Source #

sDayPoly :: forall (r1 :: Poly) (r2 :: Poly). SPoly r1 -> SPoly r2 -> SPoly (DayPoly r1 r2) Source #

class KnownPoly (p :: Poly) where Source #

Methods

sPoly :: SPoly p Source #

Instances

Instances details
KnownPoly ('[] :: [Nat]) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

sPoly :: SPoly ('[] :: [Nat]) Source #

(KnownNat e, KnownPoly es) => KnownPoly (e ': es) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

sPoly :: SPoly (e ': es) Source #

withKnownPoly :: forall (r :: Poly) result. SPoly r -> (KnownPoly r => result) -> result Source #

Evaluating Poly as a Haskell Functor

data Eval (r :: Poly) x where Source #

Constructors

EHere :: forall (e :: Nat) x (es :: [Nat]). !(Finite e -> x) -> Eval (e ': es) x 
EThere :: forall (es :: [Nat]) x (e :: Nat). !(Eval es x) -> Eval (e ': es) x 

Instances

Instances details
KnownPoly r => Eq1 (Eval r) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

liftEq :: (a -> b -> Bool) -> Eval r a -> Eval r b -> Bool #

KnownPoly r => Ord1 (Eval r) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

liftCompare :: (a -> b -> Ordering) -> Eval r a -> Eval r b -> Ordering #

KnownPoly r => PTraversable (Eval r) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

ptraverseWith :: (Cartesian p, Cocartesian p) => (as -> Eval r a) -> (Eval r b -> bs) -> p a b -> p as bs Source #

Functor (Eval r) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

fmap :: (a -> b) -> Eval r a -> Eval r b #

(<$) :: a -> Eval r b -> Eval r a #

KnownPoly r => Foldable (Eval r) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

fold :: Monoid m => Eval r m -> m #

foldMap :: Monoid m => (a -> m) -> Eval r a -> m #

foldMap' :: Monoid m => (a -> m) -> Eval r a -> m #

foldr :: (a -> b -> b) -> b -> Eval r a -> b #

foldr' :: (a -> b -> b) -> b -> Eval r a -> b #

foldl :: (b -> a -> b) -> b -> Eval r a -> b #

foldl' :: (b -> a -> b) -> b -> Eval r a -> b #

foldr1 :: (a -> a -> a) -> Eval r a -> a #

foldl1 :: (a -> a -> a) -> Eval r a -> a #

toList :: Eval r a -> [a] #

null :: Eval r a -> Bool #

length :: Eval r a -> Int #

elem :: Eq a => a -> Eval r a -> Bool #

maximum :: Ord a => Eval r a -> a #

minimum :: Ord a => Eval r a -> a #

sum :: Num a => Eval r a -> a #

product :: Num a => Eval r a -> a #

KnownPoly r => Traversable (Eval r) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

traverse :: Applicative f => (a -> f b) -> Eval r a -> f (Eval r b) #

sequenceA :: Applicative f => Eval r (f a) -> f (Eval r a) #

mapM :: Monad m => (a -> m b) -> Eval r a -> m (Eval r b) #

sequence :: Monad m => Eval r (m a) -> m (Eval r a) #

(KnownPoly r, Eq a) => Eq (Eval r a) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

(==) :: Eval r a -> Eval r a -> Bool #

(/=) :: Eval r a -> Eval r a -> Bool #

(KnownPoly r, Ord a) => Ord (Eval r a) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

compare :: Eval r a -> Eval r a -> Ordering #

(<) :: Eval r a -> Eval r a -> Bool #

(<=) :: Eval r a -> Eval r a -> Bool #

(>) :: Eval r a -> Eval r a -> Bool #

(>=) :: Eval r a -> Eval r a -> Bool #

max :: Eval r a -> Eval r a -> Eval r a #

min :: Eval r a -> Eval r a -> Eval r a #

Correspondence between sums, products, and Day convolution of Poly and its evaluation

absurdEval :: Eval ('[] :: [Nat]) a -> b Source #

unitEval :: Eval '[0] a Source #

fromSum :: forall (r1 :: Poly) proxy (r2 :: Poly) x. SPoly r1 -> proxy r2 -> Either (Eval r1 x) (Eval r2 x) -> Eval (r1 ++ r2) x Source #

inlEval :: forall (r1 :: Poly) proxy (r2 :: [Nat]) x. SPoly r1 -> proxy r2 -> Eval r1 x -> Eval (r1 ++ r2) x Source #

inrEval :: forall (r1 :: Poly) proxy (r2 :: Poly) x. SPoly r1 -> proxy r2 -> Eval r2 x -> Eval (r1 ++ r2) x Source #

toSum :: forall (r1 :: Poly) proxy (r2 :: [Nat]) x. SPoly r1 -> proxy r2 -> Eval (r1 ++ r2) x -> Either (Eval r1 x) (Eval r2 x) Source #

fromProduct :: forall (r1 :: Poly) (r2 :: Poly) x. SPoly r1 -> SPoly r2 -> Eval r1 x -> Eval r2 x -> Eval (MultPoly r1 r2) x Source #

toProduct :: forall (r1 :: Poly) (r2 :: Poly) x. SPoly r1 -> SPoly r2 -> Eval (MultPoly r1 r2) x -> (Eval r1 x, Eval r2 x) Source #

fromDay :: forall (r1 :: Poly) (r2 :: Poly) x. SPoly r1 -> SPoly r2 -> Day (Eval r1) (Eval r2) x -> Eval (DayPoly r1 r2) x Source #

toDay :: forall (r1 :: Poly) (r2 :: Poly) x. SPoly r1 -> SPoly r2 -> Eval (DayPoly r1 r2) x -> Day (Eval r1) (Eval r2) x Source #

Profunctor traversal

ptraverseEval :: forall p (r :: Poly) a b. (Cartesian p, Cocartesian p) => SPoly r -> p a b -> p (Eval r a) (Eval r b) Source #

Building bidirectional encodings as a Eval r with Profunctor

data Encoder a b s t where Source #

Constructors

Encoder :: forall (r :: Poly) s a b t. !(SPoly r) -> (s -> Eval r a) -> (Eval r b -> t) -> Encoder a b s t 

Instances

Instances details
Cartesian (Encoder a b) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

proUnit :: Encoder a b a0 () Source #

proProduct :: (a0 -> (a1, a2)) -> ((b1, b2) -> b0) -> Encoder a b a1 b1 -> Encoder a b a2 b2 -> Encoder a b a0 b0 Source #

(***) :: Encoder a b a0 b0 -> Encoder a b a' b' -> Encoder a b (a0, a') (b0, b') Source #

(&&&) :: Encoder a b a0 b0 -> Encoder a b a0 b' -> Encoder a b a0 (b0, b') Source #

proPower :: forall (n :: Nat) a0 b0. KnownNat n => Encoder a b a0 b0 -> Encoder a b (Finite n -> a0) (Finite n -> b0) Source #

Cocartesian (Encoder a b) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

proEmpty :: Encoder a b Void b0 Source #

proSum :: (a0 -> Either a1 a2) -> (Either b1 b2 -> b0) -> Encoder a b a1 b1 -> Encoder a b a2 b2 -> Encoder a b a0 b0 Source #

(+++) :: Encoder a b a0 b0 -> Encoder a b a' b' -> Encoder a b (Either a0 a') (Either b0 b') Source #

(|||) :: Encoder a b a0 b0 -> Encoder a b a' b0 -> Encoder a b (Either a0 a') b0 Source #

proTimes :: forall (n :: Nat) a0 b0. KnownNat n => Encoder a b a0 b0 -> Encoder a b (Finite n, a0) (Finite n, b0) Source #

Profunctor (Encoder a b) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

dimap :: (a0 -> b0) -> (c -> d) -> Encoder a b b0 c -> Encoder a b a0 d #

lmap :: (a0 -> b0) -> Encoder a b b0 c -> Encoder a b a0 c #

rmap :: (b0 -> c) -> Encoder a b a0 b0 -> Encoder a b a0 c #

(#.) :: forall a0 b0 c q. Coercible c b0 => q b0 c -> Encoder a b a0 b0 -> Encoder a b a0 c #

(.#) :: forall a0 b0 c q. Coercible b0 a0 => Encoder a b b0 c -> q a0 b0 -> Encoder a b a0 c #

Functor (Encoder a b s) Source # 
Instance details

Defined in Data.Finitary.PolyRep

Methods

fmap :: (a0 -> b0) -> Encoder a b s a0 -> Encoder a b s b0 #

(<$) :: a0 -> Encoder a b s b0 -> Encoder a b s a0 #

idEncoder :: Encoder a b a b Source #

Encoder for the identity functor.

It can be used to construct an encoder for arbitrary PTraversable functor using

  ptraverse idEncoder :: PTraversable t => Encoder a b (t a) (t b)

.

Internal-only type families

(++) :: [a] -> [a] -> [a] infixr 5 #

(++) appends two lists, i.e.,

[x1, ..., xm] ++ [y1, ..., yn] == [x1, ..., xm, y1, ..., yn]
[x1, ..., xm] ++ [y1, ...] == [x1, ..., xm, y1, ...]

If the first list is not finite, the result is the first list.

Performance considerations

Expand

This function takes linear time in the number of elements of the first list. Thus it is better to associate repeated applications of (++) to the right (which is the default behaviour): xs ++ (ys ++ zs) or simply xs ++ ys ++ zs, but not (xs ++ ys) ++ zs. For the same reason concat = foldr (++) [] has linear performance, while foldl (++) [] is prone to quadratic slowdown

Examples

Expand
>>> [1, 2, 3] ++ [4, 5, 6]
[1,2,3,4,5,6]

>>> [] ++ [1, 2, 3]
[1,2,3]

>>> [3, 2, 1] ++ []
[3,2,1]

type family MultPoly1 (e :: Nat) (r2 :: Poly) :: Poly where ... Source #

Equations

MultPoly1 _1 ('[] :: [Nat]) = '[] :: [Nat] 
MultPoly1 e (f ': fs) = (e + f) ': MultPoly1 e fs 

type family DayPoly1 (e :: Nat) (r2 :: Poly) :: Poly where ... Source #

Equations

DayPoly1 _1 ('[] :: [Nat]) = '[] :: [Nat] 
DayPoly1 e (f ': fs) = (e * f) ': DayPoly1 e fs