{-# LANGUAGE AllowAmbiguousTypes #-}

-- | Relations and weighted graphs on a bare set of points, given as a table: a list of edges with
-- their weights in the enriching category @v@. 'Edges' is an enriched profunctor on the discrete
-- category of an 'Indexed' kind (over a discrete base there is nothing to be compatible with), so
-- it composes, and its Kleene closure 'Proarrow.Category.Enriched.Thin.Composition.Closure' is
-- reachability for 'BOOL' weights and shortest paths for 'COST' weights.
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 (..))

-- | A weighted graph on the bare set of points of an 'Indexed' kind, given as a list of edges with
-- their weights in @v@: an enriched profunctor on the discrete category, since over a discrete base
-- there is nothing to be compatible with. Unlisted pairs are at 'InitialObject', a pair listed twice
-- takes its first weight, and an element is a pair at 'Unit' weight.
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

-- | The source of an edge.
type EdgeSrc :: forall {k} {v}. (k, k, v) -> k
type family EdgeSrc e where
  EdgeSrc '(x, y, w) = x

-- | The target of an edge.
type EdgeTgt :: forall {k} {v}. (k, k, v) -> k
type family EdgeTgt e where
  EdgeTgt '(x, y, w) = y

-- | The weight of an edge.
type EdgeWeight :: forall {k} {v}. (k, k, v) -> v
type family EdgeWeight e where
  EdgeWeight '(x, y, w) = w

-- | An edge whose endpoints are known and whose weight is an object.
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

-- | The edge list, reflected to the value level.
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

-- | The weight of a pair, found by walking the edge list: the first continuation when the pair is
-- not listed, the second with the weight when it is.
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

-- | A graph with 'BOOL' weights is a relation on the points: decided by walking the edge list.
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

-- | The weight of a pair, reflected to the value level by walking the edge list.
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

-- | A unit into a weight is an edge at the unit, since an object above the unit is the unit.
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

-- | A graph with 'COST' weights: a weighted graph, whose closure is shortest paths.
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))