{-# LANGUAGE AllowAmbiguousTypes #-}

-- | Internal module of "Proarrow.Tools.SMC": @do@ notation, including @rec@ blocks. It exports
-- everything, also what the public module keeps hidden.
module Proarrow.Tools.SMC.Internal.Do where

import Data.Kind (Constraint, Type)
import GHC.TypeNats (Nat, type (+))
import Proarrow.Category.Monoidal (Monoidal (..), MonoidalProfunctor, SymMonoidal, Tensor)
import Proarrow.Category.Monoidal qualified as M
import Proarrow.Category.Monoidal.Dialogue (Dialogue (..))
import Proarrow.Category.Monoidal.Strength (Costrong (..))
import Proarrow.Core (CAT, Hom, Profunctor (..), Promonad (..))
import Prelude (type (~))
import Prelude qualified as P

import Proarrow.Tools.SMC.Internal.Context
import Proarrow.Tools.SMC.Internal.Pattern
import Proarrow.Tools.SMC.Internal.Syntax
import Proarrow.Tools.SMC.Internal.Term

-- Do notation

-- | A bind in a @do@ block: a term, constant or tuple taken apart by a pattern, or the variables
-- of a @rec@ block.
type Bind :: forall {k}. CAT k -> Type -> Type -> Type -> Type -> Constraint
class Bind p m t cont r | m -> p where
  -- | Bind the right hand side to the pattern of the continuation.
  (>>=) :: m -> (t -> cont) -> r

-- | A term on the right hand side is taken apart by the pattern. Incoherent, so that it is chosen
-- as soon as the right hand side is known, unless the right hand side is a computation.
instance {-# INCOHERENT #-} (BindTerm p t (TermP p d g a) cont r) => Bind p (TermP p d g (a :: SYN k)) t cont r where
  {-# INLINE (>>=) #-}
  >>= :: TermP p d g a -> (t -> cont) -> r
(>>=) = forall {k} (p :: CAT k) t m cont r.
BindTerm p t m cont r =>
m -> (t -> cont) -> r
forall (p :: CAT k) t m cont r.
BindTerm p t m cont r =>
m -> (t -> cont) -> r
bindTerm @p @t

-- | Bind a constant arrow, computing it once before the continuation.
instance
  {-# OVERLAPPABLE #-}
  (p ~ q, a ~ Unit, Bind p (TermP p d '[] (F b)) t cont r)
  => Bind p (q a b) t cont r
  where
  {-# INLINE (>>=) #-}
  q a b
f >>= :: q a b -> (t -> cont) -> r
>>= t -> cont
k = (q a b -> TermP p d '[] (F b)
forall {k} (p :: CAT k) t (d :: Nat) (g :: Ctx k) (a :: SYN k).
ToTerm p t d g a =>
t -> TermP p d g a
toTerm q a b
f :: TermP p d '[] (F b)) TermP p d '[] (F b) -> (t -> cont) -> r
forall {k} (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
>>= t -> cont
k

-- A tuple's first term or arrow identifies its promonad. Unit components are skipped;
-- nested tuples are visited from left to right, with the remaining components kept in the list.
type TupleProfunctor :: [Type] -> CAT k -> Constraint
class TupleProfunctor ts p | ts -> p

instance TupleProfunctor (TermP p d g a ': ts) p
instance {-# OVERLAPPABLE #-} (p ~ q) => TupleProfunctor (q a b ': ts) p
instance {-# INCOHERENT #-} (TupleProfunctor ts p) => TupleProfunctor (() ': ts) p
instance {-# INCOHERENT #-} (TupleProfunctor (x ': y ': ts) p) => TupleProfunctor ((x, y) ': ts) p
instance {-# INCOHERENT #-} (TupleProfunctor (((x, y), z) ': ts) p) => TupleProfunctor ((x, y, z) ': ts) p
instance {-# INCOHERENT #-} (TupleProfunctor (((w, x, y), z) ': ts) p) => TupleProfunctor ((w, x, y, z) ': ts) p
instance {-# INCOHERENT #-} (TupleProfunctor (((v, w, x, y), z) ': ts) p) => TupleProfunctor ((v, w, x, y, z) ': ts) p
instance {-# INCOHERENT #-} (TupleProfunctor (((u, v, w, x, y), z) ': ts) p) => TupleProfunctor ((u, v, w, x, y, z) ': ts) p

-- | Convert a tuple before binding it. At least one component must identify the promonad.
instance
  {-# INCOHERENT #-}
  (TupleProfunctor '[x, y] p, ToTerm p (x, y) d g a, Bind p (TermP p d g a) t cont r)
  => Bind p (x, y) t cont r
  where
  {-# INLINE (>>=) #-}
  (x, y)
xy >>= :: (x, y) -> (t -> cont) -> r
>>= t -> cont
k = forall {k} (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
forall (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
(>>=) @p (forall {k} (p :: CAT k) t (d :: Nat) (g :: Ctx k) (a :: SYN k).
ToTerm p t d g a =>
t -> TermP p d g a
forall (p :: CAT k) t (d :: Nat) (g :: Ctx k) (a :: SYN k).
ToTerm p t d g a =>
t -> TermP p d g a
toTerm @p @(x, y) @d @g @a (x, y)
xy) t -> cont
k

instance {-# INCOHERENT #-} (Bind p ((x, y), z) t cont r) => Bind p (x, y, z) t cont r where
  {-# INLINE (>>=) #-}
  (x
x, y
y, z
z) >>= :: (x, y, z) -> (t -> cont) -> r
>>= t -> cont
k = forall {k} (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
forall (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
(>>=) @p ((x
x, y
y), z
z) t -> cont
k

instance {-# INCOHERENT #-} (Bind p ((w, x, y), z) t cont r) => Bind p (w, x, y, z) t cont r where
  {-# INLINE (>>=) #-}
  (w
w, x
x, y
y, z
z) >>= :: (w, x, y, z) -> (t -> cont) -> r
>>= t -> cont
k = forall {k} (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
forall (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
(>>=) @p ((w
w, x
x, y
y), z
z) t -> cont
k

instance {-# INCOHERENT #-} (Bind p ((v, w, x, y), z) t cont r) => Bind p (v, w, x, y, z) t cont r where
  {-# INLINE (>>=) #-}
  (v
v, w
w, x
x, y
y, z
z) >>= :: (v, w, x, y, z) -> (t -> cont) -> r
>>= t -> cont
k = forall {k} (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
forall (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
(>>=) @p ((v
v, w
w, x
x, y
y), z
z) t -> cont
k

instance {-# INCOHERENT #-} (Bind p ((u, v, w, x, y), z) t cont r) => Bind p (u, v, w, x, y, z) t cont r where
  {-# INLINE (>>=) #-}
  (u
u, v
v, w
w, x
x, y
y, z
z) >>= :: (u, v, w, x, y, z) -> (t -> cont) -> r
>>= t -> cont
k = forall {k} (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
forall (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
(>>=) @p ((u
u, v
v, w
w, x
x, y
y), z
z) t -> cont
k

-- | A bind of a term, by its pattern. A variable pattern binds a new variable, so that the right
-- hand side is computed once however often the variable is used. The other patterns take the
-- right hand side apart into new variables already.
type BindTerm :: forall {k}. CAT k -> Type -> Type -> Type -> Type -> Constraint
class BindTerm p t m cont r where
  bindTerm :: m -> (t -> cont) -> r

-- The instances are incoherent, as for patterns: a variable pattern's type is often still unknown
-- when the instance is chosen.

instance
  {-# INCOHERENT #-}
  (Promonad p, MonoidalProfunctor p, Binds p d r a b t cont, Merge r g, r' ~ TermP p d (Union r g) b)
  => BindTerm p t (TermP p d g (a :: SYN k)) cont r'
  where
  {-# INLINE bindTerm #-}
  bindTerm :: TermP p d g a -> (t -> cont) -> r'
bindTerm (MkTerm p (Interp (Mul g)) (Interp a)
m) t -> cont
k =
    forall (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
forall {k} (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
withCtxOb @r (p (Interp (Mul (Union r g))) (Interp b) -> TermP p d (Union r g) b
forall {k} (p :: CAT k) (g :: Ctx k) (a :: SYN k) (d :: Nat).
p (Interp (Mul g)) (Interp a) -> TermP p d g a
MkTerm (forall {k} (p :: CAT k) (n :: Nat) (g :: Ctx k) (a :: SYN k)
       (b :: SYN k) t cont.
Binds p n g a b t cont =>
(t -> cont) -> p (Interp (Mul g) ** Interp a) (Interp b)
forall (p :: CAT k) (n :: Nat) (g :: Ctx k) (a :: SYN k)
       (b :: SYN k) t cont.
Binds p n g a b t cont =>
(t -> cont) -> p (Interp (Mul g) ** Interp a) (Interp b)
bound @p @d @r @a @b t -> cont
k p (Interp (Mul r) ** Interp a) (Interp b)
-> p (Interp (Mul (Union r g))) (Interp (Mul r) ** Interp a)
-> p (Interp (Mul (Union r g))) (Interp b)
forall (b :: k) (c :: k) (a :: k). p b c -> p a b -> p a c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. (Interp (Mul (Union r g)) ~> (Interp (Mul r) ** Interp (Mul g)))
-> p (Interp (Mul r) ** Interp (Mul g))
     (Interp (Mul r) ** Interp a)
-> p (Interp (Mul (Union r g))) (Interp (Mul r) ** Interp a)
forall (c :: k) (a :: k) (b :: k). (c ~> a) -> p a b -> p c b
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j).
Profunctor p =>
(c ~> a) -> p a b -> p c b
lmap (forall (g1 :: Ctx k) (g2 :: Ctx k).
Merge g1 g2 =>
Interp (Mul (Union g1 g2)) ~> (Interp (Mul g1) ** Interp (Mul g2))
forall {k} (g1 :: Ctx k) (g2 :: Ctx k).
Merge g1 g2 =>
Interp (Mul (Union g1 g2)) ~> (Interp (Mul g1) ** Interp (Mul g2))
merge @r @g) (forall {k} (p :: CAT k) (a :: k). (Promonad p, Ob a) => p a a
forall (p :: CAT k) (a :: k). (Promonad p, Ob a) => p a a
id @p @(Interp (Mul r)) p (Interp (Mul r)) (Interp (Mul r))
-> p (Interp (Mul g)) (Interp a)
-> p (Interp (Mul r) ** Interp (Mul g))
     (Interp (Mul r) ** Interp a)
forall (x1 :: k) (x2 :: k) (y1 :: k) (y2 :: k).
p x1 x2 -> p y1 y2 -> p (x1 ** y1) (x2 ** y2)
forall {j} {k} (p :: j +-> k) (x1 :: k) (x2 :: j) (y1 :: k)
       (y2 :: j).
MonoidalProfunctor p =>
p x1 x2 -> p y1 y2 -> p (x1 ** y1) (x2 ** y2)
M.** p (Interp (Mul g)) (Interp a)
m)))

instance
  {-# INCOHERENT #-}
  (BindPat p (TermP p d g a) (x, y) cont r)
  => BindTerm p (x, y) (TermP p d g (a :: SYN k)) cont r
  where
  {-# INLINE bindTerm #-}
  bindTerm :: TermP p d g a -> ((x, y) -> cont) -> r
bindTerm = TermP p d g a -> ((x, y) -> cont) -> r
forall {k} (p :: CAT k) m t cont r.
BindPat p m t cont r =>
m -> (t -> cont) -> r
bindPat

instance
  {-# INCOHERENT #-}
  (BindPat p (TermP p d g a) (x, y, z) cont r)
  => BindTerm p (x, y, z) (TermP p d g (a :: SYN k)) cont r
  where
  {-# INLINE bindTerm #-}
  bindTerm :: TermP p d g a -> ((x, y, z) -> cont) -> r
bindTerm = TermP p d g a -> ((x, y, z) -> cont) -> r
forall {k} (p :: CAT k) m t cont r.
BindPat p m t cont r =>
m -> (t -> cont) -> r
bindPat

instance
  {-# INCOHERENT #-}
  (BindPat p (TermP p d g a) (w, x, y, z) cont r)
  => BindTerm p (w, x, y, z) (TermP p d g (a :: SYN k)) cont r
  where
  {-# INLINE bindTerm #-}
  bindTerm :: TermP p d g a -> ((w, x, y, z) -> cont) -> r
bindTerm = TermP p d g a -> ((w, x, y, z) -> cont) -> r
forall {k} (p :: CAT k) m t cont r.
BindPat p m t cont r =>
m -> (t -> cont) -> r
bindPat

instance
  {-# INCOHERENT #-}
  (BindPat p (TermP p d g a) (v, w, x, y, z) cont r)
  => BindTerm p (v, w, x, y, z) (TermP p d g (a :: SYN k)) cont r
  where
  {-# INLINE bindTerm #-}
  bindTerm :: TermP p d g a -> ((v, w, x, y, z) -> cont) -> r
bindTerm = TermP p d g a -> ((v, w, x, y, z) -> cont) -> r
forall {k} (p :: CAT k) m t cont r.
BindPat p m t cont r =>
m -> (t -> cont) -> r
bindPat

instance
  {-# INCOHERENT #-}
  (BindPat p (TermP p d g a) (u, v, w, x, y, z) cont r)
  => BindTerm p (u, v, w, x, y, z) (TermP p d g (a :: SYN k)) cont r
  where
  {-# INLINE bindTerm #-}
  bindTerm :: TermP p d g a -> ((u, v, w, x, y, z) -> cont) -> r
bindTerm = TermP p d g a -> ((u, v, w, x, y, z) -> cont) -> r
forall {k} (p :: CAT k) m t cont r.
BindPat p m t cont r =>
m -> (t -> cont) -> r
bindPat

instance
  {-# INCOHERENT #-}
  (BindPat p (TermP p d g a) () cont r)
  => BindTerm p () (TermP p d g (a :: SYN k)) cont r
  where
  {-# INLINE bindTerm #-}
  bindTerm :: TermP p d g a -> (() -> cont) -> r
bindTerm = TermP p d g a -> (() -> cont) -> r
forall {k} (p :: CAT k) m t cont r.
BindPat p m t cont r =>
m -> (t -> cont) -> r
bindPat

-- An explicit consumer determines what it consumes. An embedded dual object instead
-- uses the negative result expected by the surrounding computation.
type Negative :: forall {k}. SYN k -> SYN k -> Constraint
class (Interp c ~ Dual (Interp y)) => Negative c y

instance (y ~ y') => Negative (Not y') y
instance (f ~ Dual (Interp y)) => Negative (F f) y

-- | A computation on the right hand side runs first, and the rest of the block is negative.
instance
  ( p ~ Hom k
  , Dialogue k
  , KnownObj y
  , Merge g r
  , Negative (TyOf @k cont) y
  , Binds p d r a (TyOf @k cont) t cont
  , r' ~ TermP p d (Union g r) (Not y)
  )
  => Bind p (TermP p d g (Not (Not a) :: SYN k)) t cont r'
  where
  {-# INLINE (>>=) #-}
  TermP p d g (Not (Not a))
m >>= :: TermP p d g (Not (Not a)) -> (t -> cont) -> r'
>>= t -> cont
k = forall (d :: Nat) (g :: Ctx k) (r :: Ctx k) (a :: SYN k)
       (y :: SYN k).
(Dialogue k, KnownObj a, KnownObj y, Merge g r) =>
Term d g (Up a)
-> ((Interp (Mul r) ** Interp a) ~> Interp (Not y))
-> Term d (Union g r) (Not y)
forall {k} (d :: Nat) (g :: Ctx k) (r :: Ctx k) (a :: SYN k)
       (y :: SYN k).
(Dialogue k, KnownObj a, KnownObj y, Merge g r) =>
Term d g (Up a)
-> ((Interp (Mul r) ** Interp a) ~> Interp (Not y))
-> Term d (Union g r) (Not y)
runUp @d @g @r @a @y TermP p d g (Not (Not a))
Term d g (Not (Not a))
m (forall {k} (p :: CAT k) (n :: Nat) (g :: Ctx k) (a :: SYN k)
       (b :: SYN k) t cont.
Binds p n g a b t cont =>
(t -> cont) -> p (Interp (Mul g) ** Interp a) (Interp b)
forall (p :: CAT k) (n :: Nat) (g :: Ctx k) (a :: SYN k)
       (b :: SYN k) t cont.
Binds p n g a b t cont =>
(t -> cont) -> p (Interp (Mul g) ** Interp a) (Interp b)
bound @p @d @r @a @(TyOf @k cont) t -> cont
k)

-- | The statement of a @rec@ block, whose continuation is its 'return'.
instance
  (Bind p (TermP p d g a) t cont r', r ~ Ret tt r')
  => Bind p (TermP p d g (a :: SYN k)) t (Ret tt cont) r
  where
  {-# INLINE (>>=) #-}
  TermP p d g a
x >>= :: TermP p d g a -> (t -> Ret tt cont) -> r
>>= t -> Ret tt cont
k = r' -> Ret tt r'
forall t x. x -> Ret t x
Ret (TermP p d g a
x TermP p d g a -> (t -> cont) -> r'
forall {k} (p :: CAT k) m t cont r.
Bind p m t cont r =>
m -> (t -> cont) -> r
>>= \t
p -> Ret tt cont -> cont
forall t x. Ret t x -> x
unRet (t -> Ret tt cont
k t
p))

-- | The body of a @rec@ block, tagged with the tuple of its variables. GHC's translation passes
-- that tuple to both 'return' and 'mfix', and this tag is what makes them the same.
type Ret :: Type -> Type -> Type
newtype Ret t x = Ret x

unRet :: Ret t x -> x
unRet :: forall t x. Ret t x -> x
unRet (Ret x
x) = x
x

-- | The variables of a @rec@ block, as GHC tuples them up.
type RecVars :: Type -> Type -> Constraint
-- The empty tuple contains no term from which to recover the category.
class RecVars k t where
  type Vars k t :: Ctx k
  recVars :: t

instance RecVars k () where
  type Vars k () = '[]
  {-# INLINE recVars #-}
  recVars :: ()
recVars = ()

instance (Promonad p, KnownObj (a :: SYN k)) => RecVars k (TermP (p :: CAT k) d '[ '(n, a)] a) where
  {-# INLINE recVars #-}
  type Vars k (TermP p d '[ '(n, a)] a) = '[ '(n, a)]
  recVars :: TermP p d '[ '(n, a)] a
recVars = forall (n :: Nat) (a :: SYN k) (d :: Nat) (p :: CAT k).
(Promonad p, KnownObj a) =>
TermP p d '[ '(n, a)] a
forall {k} (n :: Nat) (a :: SYN k) (d :: Nat) (p :: CAT k).
(Promonad p, KnownObj a) =>
TermP p d '[ '(n, a)] a
var @n @a

instance (RecVars k x, RecVars k y) => RecVars k (x, y) where
  {-# INLINE recVars #-}
  type Vars k (x, y) = Union (Vars k x) (Vars k y)
  recVars :: (x, y)
recVars = (forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k)

instance (RecVars k x, RecVars k y, RecVars k z) => RecVars k (x, y, z) where
  {-# INLINE recVars #-}
  type Vars k (x, y, z) = Union (Vars k x) (Vars k (y, z))
  recVars :: (x, y, z)
recVars = (forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k)

instance (RecVars k x, RecVars k y, RecVars k z, RecVars k w) => RecVars k (x, y, z, w) where
  {-# INLINE recVars #-}
  type Vars k (x, y, z, w) = Union (Vars k x) (Vars k (y, z, w))
  recVars :: (x, y, z, w)
recVars = (forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k)

instance (RecVars k x, RecVars k y, RecVars k z, RecVars k w, RecVars k v) => RecVars k (x, y, z, w, v) where
  {-# INLINE recVars #-}
  type Vars k (x, y, z, w, v) = Union (Vars k x) (Vars k (y, z, w, v))
  recVars :: (x, y, z, w, v)
recVars = (forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k)

instance
  (RecVars k x, RecVars k y, RecVars k z, RecVars k w, RecVars k v, RecVars k u)
  => RecVars k (x, y, z, w, v, u)
  where
  {-# INLINE recVars #-}
  type Vars k (x, y, z, w, v, u) = Union (Vars k x) (Vars k (y, z, w, v, u))
  recVars :: (x, y, z, w, v, u)
recVars = (forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k, forall k t. RecVars k t => t
recVars @k)

-- | The variables of a @rec@ block again, at a depth of their own: the rest of the block uses them
-- deeper than the block did. It is asked for both ways, so that what is known about the variables
-- on either side of the block determines the other.
type AnyDepth :: Type -> Type -> Constraint
class AnyDepth t t'

instance (t' ~ ()) => AnyDepth () t'

instance (t' ~ TermP p d' g a) => AnyDepth (TermP p d g a) t'

instance (AnyDepth x x', AnyDepth y y', t' ~ (x', y')) => AnyDepth (x, y) t'

instance (AnyDepth x x', AnyDepth y y', AnyDepth z z', t' ~ (x', y', z')) => AnyDepth (x, y, z) t'

instance (AnyDepth x x', AnyDepth y y', AnyDepth z z', AnyDepth w w', t' ~ (x', y', z', w')) => AnyDepth (x, y, z, w) t'

instance
  (AnyDepth x x', AnyDepth y y', AnyDepth z z', AnyDepth w w', AnyDepth v v', t' ~ (x', y', z', w', v'))
  => AnyDepth (x, y, z, w, v) t'

instance
  ( AnyDepth x x'
  , AnyDepth y y'
  , AnyDepth z z'
  , AnyDepth w w'
  , AnyDepth v v'
  , AnyDepth u u'
  , t' ~ (x', y', z', w', v', u')
  )
  => AnyDepth (x, y, z, w, v, u) t'

-- | The end of a @rec@ block: all its variables, as the tensor of their context.
{-# INLINE return #-}
return
  :: forall k t d (p :: CAT k)
   . (Monoidal k, Promonad p, RecVars k t, KnownCtx (Vars k t))
  => t -> Ret t (TermP p d (Vars k t) (Mul (Vars k t)))
return :: forall k t (d :: Nat) (p :: CAT k).
(Monoidal k, Promonad p, RecVars k t, KnownCtx (Vars k t)) =>
t -> Ret t (TermP p d (Vars k t) (Mul (Vars k t)))
return t
_ = forall (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
forall {k} (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
withCtxOb @(Vars k t) (TermP p d (Vars k t) (Mul (Vars k t))
-> Ret t (TermP p d (Vars k t) (Mul (Vars k t)))
forall t x. x -> Ret t x
Ret (p (Interp (Mul (Vars k t))) (Interp (Mul (Vars k t)))
-> TermP p d (Vars k t) (Mul (Vars k t))
forall {k} (p :: CAT k) (g :: Ctx k) (a :: SYN k) (d :: Nat).
p (Interp (Mul g)) (Interp a) -> TermP p d g a
MkTerm (forall {k} (p :: CAT k) (a :: k). (Promonad p, Ob a) => p a a
forall (p :: CAT k) (a :: k). (Promonad p, Ob a) => p a a
id @p @(Interp (Mul (Vars k t))))))

-- | A @rec@ block before tracing: its body, from its context @g@ to all its variables. Which of them
-- are fed back and which are passed on is only known with the rest of the block, see the 'Bind'
-- instance.
type Rec :: forall {k}. CAT k -> Nat -> Type -> Ctx k -> Type
data Rec p d t g where
  Rec :: forall {k} (p :: CAT k) d t (g :: Ctx k). p (Interp (Mul g)) (Interp (Mul (Vars k t))) -> Rec p d t g

-- | The body of a @rec@ block, to be traced by the bind after it.
{-# INLINE mfix #-}
mfix
  :: forall {k} t d (g :: Ctx k) (p :: CAT k). (RecVars k t) => (t -> Ret t (TermP p d g (Mul (Vars k t)))) -> Rec p d t g
mfix :: forall {k} t (d :: Nat) (g :: Ctx k) (p :: CAT k).
RecVars k t =>
(t -> Ret t (TermP p d g (Mul (Vars k t)))) -> Rec p d t g
mfix t -> Ret t (TermP p d g (Mul (Vars k t)))
f = case Ret t (TermP p d g (Mul (Vars k t)))
-> TermP p d g (Mul (Vars k t))
forall t x. Ret t x -> x
unRet (t -> Ret t (TermP p d g (Mul (Vars k t)))
f (forall k t. RecVars k t => t
recVars @k @t)) of MkTerm p (Interp (Mul g)) (Interp (Mul (Vars k t)))
body -> p (Interp (Mul g)) (Interp (Mul (Vars k t))) -> Rec p d t g
forall {k} (p :: CAT k) (d :: Nat) t (g :: Ctx k).
p (Interp (Mul g)) (Interp (Mul (Vars k t))) -> Rec p d t g
Rec p (Interp (Mul g)) (Interp (Mul (Vars k t)))
body

-- The continuation stays at the same depth if GHC retains no variables of the block.
type RecDepth :: forall {k}. Nat -> Ctx k -> Nat
type family RecDepth d g where
  RecDepth d '[] = d
  RecDepth d ('(n, a) ': g) = n + 1

-- | The rest of the @do@ block after a @rec@ block, which traces it. The variables of the block
-- that the block itself uses are fed back, the ones the rest uses are passed on, a variable that
-- both use is copied, and one that neither uses is discarded. The rest gets the variables anew,
-- with the same ids, so that it can use them at its own depth.
instance
  ( Promonad p
  , MonoidalProfunctor p
  , Costrong Tensor p
  , SymMonoidal k
  , RecVars k t
  , AnyDepth t t'
  , AnyDepth t' t
  , RecVars k t'
  , ToTerm p cont (RecDepth d (Vars k t)) gc c
  , r ~ TermP p d (Union (Minus gc (Vars k t)) (Minus g (Vars k t))) c
  , Unmerge (Inter g (Vars k t)) (Minus g (Vars k t))
  , Union (Inter g (Vars k t)) (Minus g (Vars k t)) ~ g
  , Thin (Vars k t) (Union (Inter g (Vars k t)) (Inter gc (Vars k t)))
  , Merge (Inter g (Vars k t)) (Inter gc (Vars k t))
  , Merge (Minus gc (Vars k t)) (Minus g (Vars k t))
  , Unmerge (Minus gc (Vars k t)) (Inter gc (Vars k t))
  , Union (Minus gc (Vars k t)) (Inter gc (Vars k t)) ~ gc
  )
  => Bind p (Rec p d t (g :: Ctx k)) t' cont r
  where
  {-# INLINE (>>=) #-}
  Rec p (Interp (Mul g)) (Interp (Mul (Vars k t)))
body >>= :: Rec p d t g -> (t' -> cont) -> r
>>= t' -> cont
k = case forall {k} (p :: CAT k) t (d :: Nat) (g :: Ctx k) (a :: SYN k).
ToTerm p t d g a =>
t -> TermP p d g a
forall (p :: CAT k) t (d :: Nat) (g :: Ctx k) (a :: SYN k).
ToTerm p t d g a =>
t -> TermP p d g a
toTerm @p @cont @(RecDepth d (Vars k t)) @gc @c (t' -> cont
k (forall k t. RecVars k t => t
recVars @k @t')) of
    MkTerm p (Interp (Mul gc)) (Interp c)
rest ->
      forall (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
forall {k} (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
withCtxOb @(Minus gc (Vars k t))
        ( forall (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
forall {k} (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
withCtxOb @(Inter g (Vars k t))
            ( forall (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
forall {k} (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
withCtxOb @(Minus g (Vars k t))
                ( forall (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
forall {k} (g :: Ctx k) r.
(KnownCtx g, Monoidal k) =>
(Ob (Interp (Mul g)) => r) -> r
withCtxOb @(Inter gc (Vars k t))
                    ( p (Interp (Mul (Union (Minus gc (Vars k t)) (Minus g (Vars k t)))))
  (Interp c)
-> TermP p d (Union (Minus gc (Vars k t)) (Minus g (Vars k t))) c
forall {k} (p :: CAT k) (g :: Ctx k) (a :: SYN k) (d :: Nat).
p (Interp (Mul g)) (Interp a) -> TermP p d g a
MkTerm
                        ( p (Interp (Mul gc)) (Interp c)
rest
                            p (Interp (Mul gc)) (Interp c)
-> p (Interp
        (Mul (Union (Minus gc (Vars k t)) (Minus g (Vars k t)))))
     (Interp (Mul gc))
-> p (Interp
        (Mul (Union (Minus gc (Vars k t)) (Minus g (Vars k t)))))
     (Interp c)
forall (b :: k) (c :: k) (a :: k). p b c -> p a b -> p a c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. (Interp (Mul (Union (Minus gc (Vars k t)) (Minus g (Vars k t))))
 ~> (Interp (Mul (Minus gc (Vars k t)))
     ** Interp (Mul (Minus g (Vars k t)))))
-> ((Interp (Mul (Minus gc (Vars k t)))
     ** Interp (Mul (Inter gc (Vars k t))))
    ~> Interp (Mul gc))
-> p (Interp (Mul (Minus gc (Vars k t)))
      ** Interp (Mul (Minus g (Vars k t))))
     (Interp (Mul (Minus gc (Vars k t)))
      ** Interp (Mul (Inter gc (Vars k t))))
-> p (Interp
        (Mul (Union (Minus gc (Vars k t)) (Minus g (Vars k t)))))
     (Interp (Mul gc))
forall (c :: k) (a :: k) (b :: k) (d :: k).
(c ~> a) -> (b ~> d) -> p a b -> p c d
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j) (d :: j).
Profunctor p =>
(c ~> a) -> (b ~> d) -> p a b -> p c d
dimap
                              (forall (g1 :: Ctx k) (g2 :: Ctx k).
Merge g1 g2 =>
Interp (Mul (Union g1 g2)) ~> (Interp (Mul g1) ** Interp (Mul g2))
forall {k} (g1 :: Ctx k) (g2 :: Ctx k).
Merge g1 g2 =>
Interp (Mul (Union g1 g2)) ~> (Interp (Mul g1) ** Interp (Mul g2))
merge @(Minus gc (Vars k t)) @(Minus g (Vars k t)))
                              (forall (g1 :: Ctx k) (g2 :: Ctx k).
Unmerge g1 g2 =>
(Interp (Mul g1) ** Interp (Mul g2)) ~> Interp (Mul (Union g1 g2))
forall {k} (g1 :: Ctx k) (g2 :: Ctx k).
Unmerge g1 g2 =>
(Interp (Mul g1) ** Interp (Mul g2)) ~> Interp (Mul (Union g1 g2))
unmerge @(Minus gc (Vars k t)) @(Inter gc (Vars k t)))
                              ( forall {k} (p :: CAT k) (a :: k). (Promonad p, Ob a) => p a a
forall (p :: CAT k) (a :: k). (Promonad p, Ob a) => p a a
id @p @(Interp (Mul (Minus gc (Vars k t))))
                                  p (Interp (Mul (Minus gc (Vars k t))))
  (Interp (Mul (Minus gc (Vars k t))))
-> p (Interp (Mul (Minus g (Vars k t))))
     (Interp (Mul (Inter gc (Vars k t))))
-> p (Interp (Mul (Minus gc (Vars k t)))
      ** Interp (Mul (Minus g (Vars k t))))
     (Interp (Mul (Minus gc (Vars k t)))
      ** Interp (Mul (Inter gc (Vars k t))))
forall (x1 :: k) (x2 :: k) (y1 :: k) (y2 :: k).
p x1 x2 -> p y1 y2 -> p (x1 ** y1) (x2 ** y2)
forall {j} {k} (p :: j +-> k) (x1 :: k) (x2 :: j) (y1 :: k)
       (y2 :: j).
MonoidalProfunctor p =>
p x1 x2 -> p y1 y2 -> p (x1 ** y1) (x2 ** y2)
M.** forall {m} {k} (t :: (m, k) +-> k) (p :: k +-> k) (a :: m) (x :: k)
       (y :: k).
(Costrong t p, Ob a, Ob x, Ob y) =>
p (Act t a x) (Act t a y) -> p x y
forall (t :: (k, k) +-> k) (p :: CAT k) (a :: k) (x :: k) (y :: k).
(Costrong t p, Ob a, Ob x, Ob y) =>
p (Act t a x) (Act t a y) -> p x y
coact
                                    @Tensor
                                    @p
                                    @(Interp (Mul (Inter g (Vars k t))))
                                    @(Interp (Mul (Minus g (Vars k t))))
                                    @(Interp (Mul (Inter gc (Vars k t))))
                                    ( ((Interp (Mul (Inter g (Vars k t)))
  ** Interp (Mul (Minus g (Vars k t))))
 ~> Interp (Mul g))
-> (Interp (Mul (Vars k t))
    ~> (Interp (Mul (Inter g (Vars k t)))
        ** Interp (Mul (Inter gc (Vars k t)))))
-> p (Interp (Mul g)) (Interp (Mul (Vars k t)))
-> p (Interp (Mul (Inter g (Vars k t)))
      ** Interp (Mul (Minus g (Vars k t))))
     (Interp (Mul (Inter g (Vars k t)))
      ** Interp (Mul (Inter gc (Vars k t))))
forall (c :: k) (a :: k) (b :: k) (d :: k).
(c ~> a) -> (b ~> d) -> p a b -> p c d
forall {j} {k} (p :: j +-> k) (c :: k) (a :: k) (b :: j) (d :: j).
Profunctor p =>
(c ~> a) -> (b ~> d) -> p a b -> p c d
dimap
                                        (forall (g1 :: Ctx k) (g2 :: Ctx k).
Unmerge g1 g2 =>
(Interp (Mul g1) ** Interp (Mul g2)) ~> Interp (Mul (Union g1 g2))
forall {k} (g1 :: Ctx k) (g2 :: Ctx k).
Unmerge g1 g2 =>
(Interp (Mul g1) ** Interp (Mul g2)) ~> Interp (Mul (Union g1 g2))
unmerge @(Inter g (Vars k t)) @(Minus g (Vars k t)))
                                        ( forall (g1 :: Ctx k) (g2 :: Ctx k).
Merge g1 g2 =>
Interp (Mul (Union g1 g2)) ~> (Interp (Mul g1) ** Interp (Mul g2))
forall {k} (g1 :: Ctx k) (g2 :: Ctx k).
Merge g1 g2 =>
Interp (Mul (Union g1 g2)) ~> (Interp (Mul g1) ** Interp (Mul g2))
merge @(Inter g (Vars k t)) @(Inter gc (Vars k t))
                                            (Interp (Mul (Union (Inter g (Vars k t)) (Inter gc (Vars k t))))
 ~> (Interp (Mul (Inter g (Vars k t)))
     ** Interp (Mul (Inter gc (Vars k t)))))
-> (Interp (Mul (Vars k t))
    ~> Interp (Mul (Union (Inter g (Vars k t)) (Inter gc (Vars k t)))))
-> Interp (Mul (Vars k t))
   ~> (Interp (Mul (Inter g (Vars k t)))
       ** Interp (Mul (Inter gc (Vars k t))))
forall (b :: k) (c :: k) (a :: k). (b ~> c) -> (a ~> b) -> a ~> c
forall {k} (p :: CAT k) (b :: k) (c :: k) (a :: k).
Promonad p =>
p b c -> p a b -> p a c
. forall (g :: Ctx k) (h :: Ctx k).
Thin g h =>
Interp (Mul g) ~> Interp (Mul h)
forall {k} (g :: Ctx k) (h :: Ctx k).
Thin g h =>
Interp (Mul g) ~> Interp (Mul h)
thin @(Vars k t) @(Union (Inter g (Vars k t)) (Inter gc (Vars k t)))
                                        )
                                        p (Interp (Mul g)) (Interp (Mul (Vars k t)))
body
                                    )
                              )
                        )
                    )
                )
            )
        )

-- | GHC's translation of @rec@ refers to @fail@, but pairs of variables always match.
fail :: a
fail :: forall a. a
fail = [Char] -> a
forall a. HasCallStack => [Char] -> a
P.error [Char]
"Proarrow.Tools.SMC.fail: a pattern did not match"