代数(和微积分!)的代数数据类型

主要观点:代数数据类型(ADTs)是许多常见函数式编程语言的基础,与数学代数有相似操作,可通过计数类型的居民、代数操作、泰勒级数等方式探索其与代数的等价性,最终可将其延伸至微积分,如通过求导得到数据结构的上下文类型用于构建拉链(zipper),但对积分及求导与打孔规则相同的原因尚不清楚。
关键信息

  • 不同代数数据类型的居民数量计算方式,如Void有 0 个居民,Unit有 1 个,Bool有 2 个等。
  • 可对代数数据类型进行代数操作,如data Choice a = LeftChoice a | RightChoice a可转化为type Choice' a = (Bool, a)
  • 利用泰勒级数对ListBinaryTree数据类型进行展开,如List a可展开为1 + a + a^2 + a^3 + …BinaryTree a展开后系数为卡特兰数。
  • 发现求导与打孔数据类型的规则相似,如常数求导为 0,求和求导为各部分求导之和等。
  • 拉链是聚焦数据结构中一个元素以高效编辑的方式,求导数据结构可得到其上下文类型用于构建拉链。
    重要细节
  • Nat数据结构的分析,其方程Nat = 1 + Nat不一致,虽可展开但无法代数求解。
  • 不同数据类型中孔的数量计算规则,如无a的常量无a型孔,求和的孔数为各部分孔数之和,乘积的孔数为各位置孔数与各位置制造孔方式数的乘积。
  • 举例说明各种数据类型的具体情况,如(a, a)有 2 个a型孔,Either a a有 2 个a型孔等。
  • 提及 Conor McBride 在 2001 年注意到求导与打孔数据类型的对应关系。
  • 介绍了拉链的概念及在列表中的应用,如通过求导L = 1 + aL得到聚焦结构的类型L^2
  • 说明对积分及求导与打孔规则相同原因的困惑,目前无法给出答案。
阅读 7
0 条评论