GADT 的索引初始代数

Question

在他的论文中 Generics for the Masses Hinze 回顾了数据类型的编码。

从Nat开始

data Nat :: ⋆ where 
   Zero :: Nat
   Succ :: Nat → Nat

可以看作是NatF a = 1 + a

的初始代数NatF Nat -> Nat

它的教会代表 ∀ x. ( NatF x → x ) → x 是普遍性的见证属性由初始代数

赋予

他因此重新定义了一个等价物Nat

newtype Nat = Nat{fold :: ∀ nat . Algebra nat → nat } 
data Algebra nat = With{
  foldZero :: nat,
  foldSucc :: nat → nat }

这会产生一个函数 ∀ nat . Algebra x → (Nat → x)，它给出了初始代数的唯一代数态射。（也可以将 Nat 视为健忘函子的极限锥，并且此函数在代数类别中的每个对象处产生该锥的分量）。这是经典。

但他随后提到了以下数据类型的 Church 编码，这是一个 GADT，旨在成为类型化的类型表示

data Rep :: ⋆ → ⋆ where
  Int :: Rep Int
  Pair :: ∀α β . Rep α → Rep β → Rep (α, β)

编码为

data Rep τ = Rep{fold :: ∀rep . Algebra rep → rep τ } 
data Algebra rep = With{
  foldInt :: rep Int,
  foldPair :: ∀α β . rep α → rep β → rep (α, β) }

int:: Rep Int
int = Rep (λc → foldInt c)

pair :: ∀α β . Rep α → Rep β → Rep (α, β)
pair a b = Rep (λc → foldPair c (fold a c) (fold b c))

这种编码是什么代数？由于索引，它不是简单的代数。一些看拓赋可以表达这个普通的代数吗？

Answer 1

区别在于类别。 Nat 是类型范畴中的初始代数。 Rep 是索引类型类别中的初始代数。索引类型的类别具有 * -> * 类型的对象类型构造函数，以及 f ~> g 的态射，forall t. f t -> g t.

类型的函数

则Rep为函子RepF的初始代数定义如下：

data RepF rep :: * -> * where
  Int :: RepF rep Int
  Pair :: forall a b. rep a -> rep b -> RepF rep (a, b)

同样，Church 编码

newtype Rep t = Rep { fold :: forall rep. Algebra rep -> rep t }
type Algebra rep = RepF rep ~> rep
type f ~> g = forall t. f t -> g t

为每个 Algebra rep 生成一个映射 forall t. Rep t -> rep t。

Answer 2

这里是 Li-yao Xia 的答案的扩展版本。我的任何错误等..

除了代数之外，Hinze 的 Generics for the masses 论文涉及将它们提升为类型类，以便静态地完成计算。这种对应是直接的，独立于代数本身的编码。

论文在 Extensible and Modular Generics for the Masses 中进行了扩展，它分解了（静态）计算以更好地近似解决“表达式问题”。

U-Indexed版本

我们用

声明类型U（*的对象）

data U where
  UPair :: U -> U -> U
  UInt :: U

然后我们将它提升为一种，{-# LANGUAGE DataKinds #-}。这意味着我们将其视为一个离散类别，其对象由类型构造函数 'UInt 和 'UPair

归纳定义

这是一个从 U 到 Hask 的（归纳定义的）函子，它将 U 的每个对象映射到 Hask

的对象

data Pair α β = Pair {outl :: α, outr :: β}

data Unit = Unit

type family Star (u :: U) :: * where
  Star (UPair a b) = Pair (Star a) (Star b)
  Star UInt = Int

这是类型之间的纯映射，我们可以在类型签名中使用它

类别`(U->Hask)`

类别(U->Hask)有

对象 m :: U -> * 索引类型
对于态射 m ~> n = forall (i :: *). m i -> n i 索引类型之间的索引函数
明显的身份和构成

这里是(U->Hask)

的一个（归纳定义的）对象

data DRep :: U -> * where
  DPair :: DRep a -> DRep b -> DRep (UPair a b)
  DInt :: DRep UInt

请注意，它只是具体化（“理解”）* 中 U 的现有结构：对于 U 的每个索引，它是一个类型，被视为一个集合，U 中的每个对象都有一个元素，由构造函数定义。我们可以使用普通函数使用或生成这些类型的值。 * 本身可以被视为由 1

索引

这用“具体化 U”

说明了类型签名和计算

toStar :: DRep a -> Star a
toStar DInt = 0
toStar (DPair a b) = Pair (toStar a) (toStar b)

函子`(U->Hask) -> (U->Hask)`

仿函数将对象映射到对象，将箭头映射到箭头，更一般地说，将组合映射到组合

-- Object mapping of the endofunctor RepF :: (U->Hask) -> (U->Hask)
-- object of the source category (U->Hask) are transported to
-- object of the target category (U->Hask)
data RepF (m :: U -> *) :: U -> * where
  FPair :: m a -> m b -> RepF m (UPair a b)
  FInt :: RepF m UInt

-- Morphism mapping of endofunctors :: (U->Hask) -> (U->Hask)
-- morphisms of the source category (U->Hask) are transported to
-- morphisms in the target category (U->Hask)
-- between the transported objects
class UFunctor (h :: ((U -> *) -> U -> *)) where
  umap :: (forall (i :: U). m i -> n i) -> h m i -> h n i

-- Morphism mapping (implicit form) of the endofunctor RepF :: (U->Hask) -> (U->Hask)
instance UFunctor RepF where
  umap n = \case
    FPair ma mb -> FPair (n ma) (n mb)
    FInt -> FInt

-- We call repF the explicit action on morphism of RepF
repF :: (forall i. m i -> n i) -> RepF m i -> RepF n i
repF = umap

代数

h-algebra“在 m”或“运营商 m”，其中 m 属于 (U->Hask) 是一个态射（在(U->Hask)）

      h m ~> m

传输对象h m和m之间。更一般地，m 处的 h-algebra，其中 m 是函子 A -> (U->Hask) 是态射的集合（在 (U->Hask) 中）

     α_a :: h (m a) ~> m a

由 A 的对象 a 索引，验证 A

中任何 f: a -> b 的自然性条件 α_a;m f = h m f; α_b

type UAlg h m = forall (i :: U). h m i -> m i

-- rep is an RepF-algebra of carrier DRep
rep :: forall (x :: U). RepF DRep x -> DRep x
rep (FPair ra rb) = DPair ra rb
rep FInt = DInt

代数的初衷

初始f-algebra是代数范畴中的初始对象。它是平凡函子 !: f-Alg -> 1 到平凡范畴 1 的左伴随，表示函子 1(1, ! _) = f-Alg(I,_): f-Alg -> Set.

对于任何f-algebra，初始代数从中确定一个f-algebra态射，而且这是两者之间唯一的态射。

这属性相当于载体是函子U : f-Alg -> C的最终锥体（极限锥体）。（任何锥体都必须映射到初始代数的载体，并且映射到其他代数将通过锥体属性的映射进行因式分解。相反，作为最终锥体具有 f-alg 的表示，C::C^op->Set，由一个元素f-alg，C（代数间态射的集合）见证，终结于元素的范畴使得任意锥f-alg，C都来来自唯一态射的预合成)

-- This algebra rep is initial

-- This is a witness of initiality -- using the functor instance repF
foldRep :: (forall a. RepF m a -> m a) -> DRep x -> m x
foldRep halg = halg . repF (foldRep halg) . repinv
  where
    repinv :: DRep x -> RepF DRep x
    repinv (DPair ma mb) = FPair ma mb
    repinv DInt = FInt

作为最终锥体的普遍属性的见证是教会代表（我认为）

type UChurch t x = forall (m :: U -> *). (forall (i :: U). t m i -> m i) -> m x

Hinze 编码为

-- Church Encoding de Hinze
newtype Rep x = Rep {eval :: forall rep. ChurchAlg rep -> rep x}

data ChurchAlg (rep :: * -> *) = ChurchAlg
  { pair_ :: forall a b. rep a -> rep b -> rep (Pair a b),
    int_ :: rep Int
  }

我们可以验证这是一个专业

type URep x = UChurch RepF x
-- = forall m. (forall (a :: U). RepF m a -> m a) -> m x
-- = forall m. (
--    pair_ :: RepF m (UPair a b) -> m (UPair a b)
--    int_ :: RepF m UInt -> n UInt ) -> m x
-- = forall m. (
--    pair_ :: m a -> m b -> m (UPair a b)
--    int_ :: m UInt ) -> m x

所以Rep是由最终锥确定的初始RepF-代数的载体。 rep 是 Rep 处的初始 RepF-代数。

Hask-indexed版本

当我们用*替换U时，我们得到一个代数

-- rep is an RepF-algebra of carrier Rep
rep :: forall x. RepF Rep x -> Rep x
rep FInt = Int
rep (FPair ra rb) = Pair ra rb

当 rep 只为两个索引定义时，这怎么可能是一个代数，它需要在每个类型 a :: * 上定义？

实际上，rep 为我们选择的每个索引定义了 Hask 在该索引处的态射。让我们选择一个不是 Int 或 (a,b)

的索引

repChar (v :: RepF Rep Char) = rep @Char v

这个态射是有效的，它等于

repChar (v :: RepF Rep Char) = error "impossible"

这是由于 Hask 的特定定义，其态射是被视为一对值集的类型对之间的函数。

RepF Rep Char 类型的值集为空：它在 Hask 中是初始值。从 RepF Rep Char 到任何其他类型都有一个独特的功能，“免费”，它不映射任何内容。

GADT 的索引初始代数

Indexed Initial algebras for GADTs

haskell

types

algebra

algebraic-data-types

category-theory

U-Indexed版本

类别`(U->Hask)`

函子`(U->Hask) -> (U->Hask)`

代数

代数的初衷

Hask-indexed版本

GADT 的索引初始代数

Indexed Initial algebras for GADTs

haskell

types

algebra

algebraic-data-types

category-theory

U-Indexed版本

类别(U->Hask)

函子(U->Hask) -> (U->Hask)

代数

代数的初衷

Hask-indexed版本

类别`(U->Hask)`

函子`(U->Hask) -> (U->Hask)`