Skip to content

积类型

Product type

其值由两个分量组成并支持投影的类型。

条目类型
定义

形式陈述

给定类型 A,B,积类型 A×B 的值由一个有序对的两项分量组成。以下类型判断给出它的引入与消去规则:

Γt1:AΓt2:BΓ(t1,t2):A×B,Γt:A×BΓπ1t:A,Γt:A×BΓπ2t:B.

计算规则为 π1(v1,v2)v1π2(v1,v2)v2。在带 η-等价的系统中,t:A×B 还与 (π1t,π2t) 等价。

零元积是单位类型 1,有限多元组可由二元积嵌套得到。在范畴语义中,积还满足泛性质:给定 f:XAg:XB,存在唯一的配对映射 f,g:XA×B,其两个投影分别为 f,g

直觉

积类型表达“同时拥有一份 A 和一份 B”。构造它必须给出两个分量,使用它可独立投影任一分量;因此信息是累积而非选择性的。把它想成固定字段的二元记录最自然,更多元组只是重复嵌套或一般化。名称来自集合的笛卡尔积,但程序类型还携带求值与相等规则,不能只把它当作无语义的内存布局。

例子与边界

函数

swap=λp:A×B.(π2p,π1p)

具有类型 A×BB×A。若 p=(3,true),则 π1p3π2ptrue

边界是积类型与和类型的混淆:A×B 的每个值都同时包含两类数据,而 A+B 每次只包含某一分支。若语言有副作用,构造一对时两个分量的求值顺序仍需另行规定;类型本身不决定先算左边还是右边。

推论与应用

积类型支撑元组、记录、函数多返回值和环境结构。记录类型可看作带字段名的有限积,函数多参数也可柯里化或接收一个积类型参数。

Curry–Howard 对应下,A×B 对应合取 AB:构造一对就是同时给出两个证明,投影就是取出其中一个。积作为构造子字段的组合方式进入代数数据类型;完整的和—积—递归汇总由该页承担。

普通积允许分别投影、从而忽略另一分量。线性 tensor则在线性上下文分割下同时交付两个分量,不能无条件复用这些笛卡尔投影规则;二者的差别来自资源纪律,不是换一个乘号而已。

参考资料
  • Benjamin C. Pierce, Types and Programming Languages, MIT Press, 2002,Ch. 11, products, tuples, and records。
  • Robert Harper, Practical Foundations for Programming Languages, 2nd ed., Cambridge University Press, 2016,Ch. 11, product types。
关系图谱12 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组