{-# LANGUAGE AllowAmbiguousTypes #-}
module Proarrow.Profunctor.Instance.Edges where
import Data.Kind (Constraint)
import Data.Type.Equality qualified as Eq
import Prelude (type (~))
import Proarrow.Category.Enriched (EnrichedProfunctor (..))
import Proarrow.Category.Enriched.Quantale (Quantale (..))
import Proarrow.Category.Enriched.Thin
( DecidableProfunctor (..)
, Decision (..)
, Equal
, Indexed
, KnownIndex
, ThinProfunctor
, decideEq
)
import Proarrow.Category.Instance.Bool (BOOL (..), Booleans (..), If)
import Proarrow.Category.Instance.Cost (COST)
import Proarrow.Category.Instance.Discrete (DISCRETE (..), Discrete (..), deltaAct)
import Proarrow.Category.Monoidal (Monoidal (..))
import Proarrow.Colimit.Initial (HasInitialObject (..))
import Proarrow.Core (CategoryOf (..), Kind, Profunctor (..), obj, type (+->))
import Proarrow.Limit.BinaryProduct (type (&&))
import Proarrow.Object (KnownListOf (..), ListOf (..))
type Edges :: forall {k} {v}. [(k, k, v)] -> DISCRETE k +-> DISCRETE k
data Edges es a b where
Edge :: (Ob a, Ob b, WeightOf es a b ~ Unit) => Edges es a b
type WeightOf :: forall {k} {v}. [(k, k, v)] -> DISCRETE k -> DISCRETE k -> v
type family WeightOf es a b where
WeightOf '[] a b = InitialObject
WeightOf ('(x, y, w) ': es) a b = If (Equal a (D x) && Equal b (D y)) w (WeightOf es a b)
instance (Indexed k) => Profunctor (Edges (es :: [(k, k, v)])) where
dimap :: forall (c :: DISCRETE k) (a :: DISCRETE k) (b :: DISCRETE k)
(d :: DISCRETE k).
(c ~> a) -> (b ~> d) -> Edges es a b -> Edges es c d
dimap c ~> a
Discrete c a
Refl b ~> d
Discrete b d
Refl Edges es a b
e = Edges es c d
Edges es a b
e
(Ob a, Ob b) => r
r \\ :: forall (a :: DISCRETE k) (b :: DISCRETE k) r.
((Ob a, Ob b) => r) -> Edges es a b -> r
\\ Edges es a b
Edge = r
(Ob a, Ob b) => r
r
type EdgeSrc :: forall {k} {v}. (k, k, v) -> k
type family EdgeSrc e where
EdgeSrc '(x, y, w) = x
type EdgeTgt :: forall {k} {v}. (k, k, v) -> k
type family EdgeTgt e where
EdgeTgt '(x, y, w) = y
type EdgeWeight :: forall {k} {v}. (k, k, v) -> v
type family EdgeWeight e where
EdgeWeight '(x, y, w) = w
type KnownEdge :: forall {k} {v}. (k, k, v) -> Constraint
class
(e ~ '(EdgeSrc e, EdgeTgt e, EdgeWeight e), KnownIndex (EdgeSrc e), KnownIndex (EdgeTgt e), Ob (EdgeWeight e)) =>
KnownEdge e
instance
(e ~ '(EdgeSrc e, EdgeTgt e, EdgeWeight e), KnownIndex (EdgeSrc e), KnownIndex (EdgeTgt e), Ob (EdgeWeight e))
=> KnownEdge e
type EdgeList :: forall k v. [(k, k, v)] -> Kind
type EdgeList @k @v = ListOf (KnownEdge :: (k, k, v) -> Constraint)
type KnownEdges :: forall {k} {v}. [(k, k, v)] -> Constraint
type KnownEdges es = KnownListOf KnownEdge es
lookupEdge
:: forall {k} {v} (es :: [(k, k, v)]) a b r
. (Indexed k, KnownIndex a, KnownIndex b)
=> EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall w. (WeightOf es a b ~ w, Ob w) => r)
-> r
lookupEdge :: forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Indexed k, KnownIndex a, KnownIndex b) =>
EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall (w :: v). (WeightOf es a b ~ w, Ob w) => r)
-> r
lookupEdge ListOf KnownEdge es
Nil (WeightOf es a b ~ InitialObject) => r
none forall (w :: v). (WeightOf es a b ~ w, Ob w) => r
_ = r
(WeightOf es a b ~ InitialObject) => r
none
lookupEdge (Cons @'(x, y, w) ListOf KnownEdge xs1
es) (WeightOf es a b ~ InitialObject) => r
none forall (w :: v). (WeightOf es a b ~ w, Ob w) => r
found = case (forall {k} (a :: k) (b :: k).
(KnownIndex a, KnownIndex b) =>
Decision (:~:) a b (Equal a b)
forall (a :: DISCRETE k) (b :: DISCRETE k).
(KnownIndex a, KnownIndex b) =>
Decision (:~:) a b (Equal a b)
decideEq @a @(D x), forall {k} (a :: k) (b :: k).
(KnownIndex a, KnownIndex b) =>
Decision (:~:) a b (Equal a b)
forall (a :: DISCRETE k) (b :: DISCRETE k).
(KnownIndex a, KnownIndex b) =>
Decision (:~:) a b (Equal a b)
decideEq @b @(D y)) of
(Yes a :~: D (EdgeSrc x)
Eq.Refl, Yes b :~: D (EdgeTgt x)
Eq.Refl) -> forall (w :: v). (WeightOf es a b ~ w, Ob w) => r
found @w
(Decision
(:~:)
a
(D (EdgeSrc x))
(NatEq (Index (UN D a)) (Index (EdgeSrc x)))
No, Decision
(:~:)
b
(D (EdgeTgt x))
(NatEq (Index (UN D b)) (Index (EdgeTgt x)))
_) -> forall (es :: [(k, k, v)]) (a :: DISCRETE k) (b :: DISCRETE k) r.
(Indexed k, KnownIndex a, KnownIndex b) =>
EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall (w :: v). (WeightOf es a b ~ w, Ob w) => r)
-> r
forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Indexed k, KnownIndex a, KnownIndex b) =>
EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall (w :: v). (WeightOf es a b ~ w, Ob w) => r)
-> r
lookupEdge @_ @a @b ListOf KnownEdge xs1
es r
(WeightOf es a b ~ InitialObject) => r
(WeightOf xs1 a b ~ InitialObject) => r
none r
forall (w :: v). (WeightOf es a b ~ w, Ob w) => r
forall (w :: v). (WeightOf xs1 a b ~ w, Ob w) => r
found
(Yes a :~: D (EdgeSrc x)
_, Decision
(:~:)
b
(D (EdgeTgt x))
(NatEq (Index (UN D b)) (Index (EdgeTgt x)))
No) -> forall (es :: [(k, k, v)]) (a :: DISCRETE k) (b :: DISCRETE k) r.
(Indexed k, KnownIndex a, KnownIndex b) =>
EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall (w :: v). (WeightOf es a b ~ w, Ob w) => r)
-> r
forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Indexed k, KnownIndex a, KnownIndex b) =>
EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall (w :: v). (WeightOf es a b ~ w, Ob w) => r)
-> r
lookupEdge @_ @a @b ListOf KnownEdge xs1
es r
(WeightOf es a b ~ InitialObject) => r
(WeightOf xs1 a b ~ InitialObject) => r
none r
forall (w :: v). (WeightOf es a b ~ w, Ob w) => r
forall (w :: v). (WeightOf xs1 a b ~ w, Ob w) => r
found
instance (Indexed k, KnownEdges es) => ThinProfunctor (Edges (es :: [(k, k, BOOL)]))
instance (Indexed k, KnownEdges es) => DecidableProfunctor (Edges (es :: [(k, k, BOOL)])) where
type Holds (Edges es) a b = WeightOf es a b
decide :: forall (a :: DISCRETE k) (b :: DISCRETE k).
(Ob a, Ob b) =>
Decision (Edges es) a b (Holds (Edges es) a b)
decide @a @b = forall (es :: [(k, k, BOOL)]) (a :: DISCRETE k) (b :: DISCRETE k)
r.
(Indexed k, KnownIndex a, KnownIndex b) =>
EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall (w :: BOOL). (WeightOf es a b ~ w, Ob w) => r)
-> r
forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Indexed k, KnownIndex a, KnownIndex b) =>
EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall (w :: v). (WeightOf es a b ~ w, Ob w) => r)
-> r
lookupEdge @es @a @b EdgeList es
forall {k} (c :: OB k) (xs :: [k]). KnownListOf c xs => ListOf c xs
listOf Decision (Edges es) a b 'FLS
Decision (Edges es) a b (WeightOf es a b)
(WeightOf es a b ~ InitialObject) =>
Decision (Edges es) a b (WeightOf es a b)
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
Decision p a b 'FLS
No \ @w -> case forall {k} (a :: k). (CategoryOf k, Ob a) => Obj a
forall (a :: BOOL). (CategoryOf BOOL, Ob a) => Obj a
obj @w of
Obj w
Booleans w w
Tru -> Edges es a b -> Decision (Edges es) a b 'TRU
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
p a b -> Decision p a b 'TRU
Yes Edges es a b
forall {k} {v} (a :: DISCRETE k) (b :: DISCRETE k)
(es :: [(k, k, v)]).
(Ob a, Ob b, WeightOf es a b ~ Unit) =>
Edges es a b
Edge
Obj w
Booleans w w
Fls -> Decision (Edges es) a b 'FLS
Decision (Edges es) a b (WeightOf es a b)
forall {j} {k} (p :: j +-> k) (a :: k) (b :: j).
Decision p a b 'FLS
No
toHolds :: forall (a :: DISCRETE k) (b :: DISCRETE k) r.
Edges es a b
-> ((Holds (Edges es) a b ~ 'TRU, Ob a, Ob b) => r) -> r
toHolds Edges es a b
Edge (Holds (Edges es) a b ~ 'TRU, Ob a, Ob b) => r
r = r
(Holds (Edges es) a b ~ 'TRU, Ob a, Ob b) => r
r
withObWeight
:: forall {k} {v} (es :: [(k, k, v)]) a b r
. (Quantale v, Indexed k, KnownEdges es, KnownIndex a, KnownIndex b)
=> ((Ob (WeightOf es a b)) => r) -> r
withObWeight :: forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Quantale v, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Ob (WeightOf es a b) => r) -> r
withObWeight Ob (WeightOf es a b) => r
r = forall (es :: [(k, k, v)]) (a :: DISCRETE k) (b :: DISCRETE k) r.
(Indexed k, KnownIndex a, KnownIndex b) =>
EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall (w :: v). (WeightOf es a b ~ w, Ob w) => r)
-> r
forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Indexed k, KnownIndex a, KnownIndex b) =>
EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall (w :: v). (WeightOf es a b ~ w, Ob w) => r)
-> r
lookupEdge @es @a @b EdgeList es
forall {k} (c :: OB k) (xs :: [k]). KnownListOf c xs => ListOf c xs
listOf r
(WeightOf es a b ~ InitialObject) => r
Ob (WeightOf es a b) => r
r r
Ob (WeightOf es a b) => r
forall (w :: v). (WeightOf es a b ~ w, Ob w) => r
r
enrichedEdge
:: forall {k} {v} (es :: [(k, k, v)]) a b
. (Quantale v, Indexed k, KnownEdges es, KnownIndex a, KnownIndex b)
=> Unit ~> WeightOf es a b -> Edges es a b
enrichedEdge :: forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k).
(Quantale v, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Unit ~> WeightOf es a b) -> Edges es a b
enrichedEdge Unit ~> WeightOf es a b
f = forall (es :: [(k, k, v)]) (a :: DISCRETE k) (b :: DISCRETE k) r.
(Indexed k, KnownIndex a, KnownIndex b) =>
EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall (w :: v). (WeightOf es a b ~ w, Ob w) => r)
-> r
forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Indexed k, KnownIndex a, KnownIndex b) =>
EdgeList es
-> ((WeightOf es a b ~ InitialObject) => r)
-> (forall (w :: v). (WeightOf es a b ~ w, Ob w) => r)
-> r
lookupEdge @es @a @b EdgeList es
forall {k} (c :: OB k) (xs :: [k]). KnownListOf c xs => ListOf c xs
listOf (forall v r. Quantale v => (Unit ~> InitialObject) -> r
unitIsNotBottom @v Unit ~> InitialObject
Unit ~> WeightOf es a b
f) \ @w -> forall v (w :: v) r.
(Quantale v, Ob w) =>
(Unit ~> w) -> ((w ~ Unit) => r) -> r
unitIsTop @v @w Unit ~> w
Unit ~> WeightOf es a b
f Edges es a b
(w ~ Unit) => Edges es a b
forall {k} {v} (a :: DISCRETE k) (b :: DISCRETE k)
(es :: [(k, k, v)]).
(Ob a, Ob b, WeightOf es a b ~ Unit) =>
Edges es a b
Edge
instance (Indexed k, KnownEdges es) => EnrichedProfunctor COST (Edges (es :: [(k, k, COST)])) where
type ProObj COST (Edges es) a b = WeightOf es a b
withProObj :: forall (a :: DISCRETE k) (b :: DISCRETE k) r.
(Ob a, Ob b) =>
(Ob (ProObj COST (Edges es) a b) => r) -> r
withProObj @a @b = forall (es :: [(k, k, COST)]) (a :: DISCRETE k) (b :: DISCRETE k)
r.
(Quantale COST, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Ob (WeightOf es a b) => r) -> r
forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Quantale v, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Ob (WeightOf es a b) => r) -> r
withObWeight @es @a @b
underlying :: forall (a :: DISCRETE k) (b :: DISCRETE k).
Edges es a b -> Unit ~> ProObj COST (Edges es) a b
underlying Edges es a b
Edge = forall {k} (a :: k). (CategoryOf k, Ob a) => Obj a
forall (a :: COST). (CategoryOf COST, Ob a) => Obj a
obj @(Unit :: COST)
enriched :: forall (a :: DISCRETE k) (b :: DISCRETE k).
(Ob a, Ob b) =>
(Unit ~> ProObj COST (Edges es) a b) -> Edges es a b
enriched @a @b = forall (es :: [(k, k, COST)]) (a :: DISCRETE k) (b :: DISCRETE k).
(Quantale COST, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Unit ~> WeightOf es a b) -> Edges es a b
forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k).
(Quantale v, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Unit ~> WeightOf es a b) -> Edges es a b
enrichedEdge @es @a @b
rmap :: forall (a :: DISCRETE k) (b :: DISCRETE k) (c :: DISCRETE k).
(Ob a, Ob b, Ob c) =>
(HomObj COST b c ** ProObj COST (Edges es) a b)
~> ProObj COST (Edges es) a c
rmap @a @b @c =
forall (es :: [(k, k, COST)]) (a :: DISCRETE k) (b :: DISCRETE k)
r.
(Quantale COST, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Ob (WeightOf es a b) => r) -> r
forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Quantale v, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Ob (WeightOf es a b) => r) -> r
withObWeight @es @a @b (forall (es :: [(k, k, COST)]) (a :: DISCRETE k) (b :: DISCRETE k)
r.
(Quantale COST, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Ob (WeightOf es a b) => r) -> r
forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Quantale v, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Ob (WeightOf es a b) => r) -> r
withObWeight @es @a @c (forall {k} {v} (x :: k) (y :: k) (w :: v) (w' :: v).
(Quantale v, KnownIndex x, KnownIndex y, Ob w, Ob w') =>
((x ~ y) => w :~: w') -> (Delta v (Equal x y) ** w) ~> w'
forall (x :: DISCRETE k) (y :: DISCRETE k) (w :: COST)
(w' :: COST).
(Quantale COST, KnownIndex x, KnownIndex y, Ob w, Ob w') =>
((x ~ y) => w :~: w') -> (Delta COST (Equal x y) ** w) ~> w'
deltaAct @b @c @(WeightOf es a b) @(WeightOf es a c) WeightOf es a b :~: WeightOf es a c
WeightOf es a c :~: WeightOf es a c
(b ~ c) => WeightOf es a b :~: WeightOf es a c
forall {k} (a :: k). a :~: a
Eq.Refl))
lmap :: forall (a :: DISCRETE k) (b :: DISCRETE k) (c :: DISCRETE k).
(Ob a, Ob b, Ob c) =>
(HomObj COST c a ** ProObj COST (Edges es) a b)
~> ProObj COST (Edges es) c b
lmap @a @b @c =
forall (es :: [(k, k, COST)]) (a :: DISCRETE k) (b :: DISCRETE k)
r.
(Quantale COST, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Ob (WeightOf es a b) => r) -> r
forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Quantale v, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Ob (WeightOf es a b) => r) -> r
withObWeight @es @a @b (forall (es :: [(k, k, COST)]) (a :: DISCRETE k) (b :: DISCRETE k)
r.
(Quantale COST, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Ob (WeightOf es a b) => r) -> r
forall {k} {v} (es :: [(k, k, v)]) (a :: DISCRETE k)
(b :: DISCRETE k) r.
(Quantale v, Indexed k, KnownEdges es, KnownIndex a,
KnownIndex b) =>
(Ob (WeightOf es a b) => r) -> r
withObWeight @es @c @b (forall {k} {v} (x :: k) (y :: k) (w :: v) (w' :: v).
(Quantale v, KnownIndex x, KnownIndex y, Ob w, Ob w') =>
((x ~ y) => w :~: w') -> (Delta v (Equal x y) ** w) ~> w'
forall (x :: DISCRETE k) (y :: DISCRETE k) (w :: COST)
(w' :: COST).
(Quantale COST, KnownIndex x, KnownIndex y, Ob w, Ob w') =>
((x ~ y) => w :~: w') -> (Delta COST (Equal x y) ** w) ~> w'
deltaAct @c @a @(WeightOf es a b) @(WeightOf es c b) WeightOf es a b :~: WeightOf es a b
WeightOf es a b :~: WeightOf es c b
(c ~ a) => WeightOf es a b :~: WeightOf es c b
forall {k} (a :: k). a :~: a
Eq.Refl))