Indexed chain/listby & commutative bifunctors

[Jashweii]

Disclaimer: I don't have a concrete use case for this, this is just a thought about how this library could cover the same ground as hlist/variant.

When you have a (directly) nested associative bifunctor application for a known finite spine a + b + c + d
there is often an efficient representation Variant '[a,b,c,d :: k -> Type] :: k -> Type. I.e. IListBy such that (exists n . IListBy t i (Replicate n a)) ~ ListBy t i a (for finite cases). I think you can always default to unsafely wrapping ListBy t GHC.Exts.Any when t is parametric in f. Would it make sense then to have type-indexed chains and lists in the library? E.g. (unchecked)

  -- foldr t i fs a, equivalent type supported by Tensor
  data IChain t i fs a where
    IDone :: i a -> IChain t i '[] a
    IMore :: t f (IChain t i fs) a -> IChain t i (f ': fs) a

  -- foldr1 t fs a, equivalent type supported by Associative
  -- basically the same as IChain t _ (_ ': fs)
  data IChain1 t fs a where
    IDone1 :: f a -> IChain1 t '[f] a
    IMore1 :: t f (IChain1 t fs) a -> IChain1 t (f ': fs) a  

Relatedly presumably there could be support for commutative bifunctors, which when associative might efficiently re-associate.

class HBifunctor t => Commutative t where
  hcommuting :: t f g <~> t g f

-- f is in fs at this index
newtype MemberOf fs f = UnsafeMemberOf Int

-- invariant: bijective. Groupoid instance
newtype Permutation fs gs = Permutation (MemberOf fs <~> MemberOf gs)

class (Commutative t, Associative t) => Abelian t where
  ipermuteNE :: Permutation fs gs -> INonEmptyBy t fs <~> INonEmptyBy t gs

class (Abelian t, Tensor t) => Monoid t where
  ipermute :: Permutation fs gs -> IListBy t fs <~> IListBy t gs

e.g.

  data IListBy (:+:) V1 fs a = forall f . IListByPlus1V1 !(MemberOf fs f) (f a)

Would just apply the permutation forwards to the index.

  data IListBy (:*:) U1 fs a = IListByTimes1U1 (forall f . MemberOf fs f -> f a)
  data IListBy These V1 fs a = IListByThese1V1 (forall f . MemberOf fs f -> Maybe (f a))

Would apply the inverse permutation to the input (function version for simplicity, alternatively a bunch of swaps/index changes)