在编程语言中，参数多态函数(不是临时多态函数)操作的全部空间是什么？

Question

在https://www.pure.ed.ac.uk/ws/files/15143545/1_s2.0_0022000078900144_main.pdf第349页第5段中，米尔纳说，

对我们来说，程序中的多态性是每种编程语言中似乎都存在的原始多态运算符的自然产物；这些运算符是赋值、函数应用、配对和元抽样以及列表处理操作符。

这个描述是否定义了全部参数多态函数(当我们将列表处理操作符扩展到所有递归数据类型上的操作符时)？(+，*，.需要以特殊的方式定义，为它们处理的每个类型提供不同的底层实现)。另外，是否有某种形式模式将参数多态函数与必须用重载(ad )定义的多态函数分离？

Answer 1

这个描述是否定义了完整的参数多态函数集？

哪儿有的事儿。当然不是。教会教导我们，有一个无限丰富的参数多态函数的集合。例如：

type Nat = forall a. (a -> a) -> a -> a

zero :: Nat
zero s z = z

succ :: Nat -> Nat
succ n s z = s (n s z)

one, two, three :: Nat
one = succ zero
two = succ one
three = succ two

所有的zero、one、two和three都是参数多态函数；它们都是不同的，因为我们可以将它们应用到不同的参数中，为每个参数提供不同的结果。这只是最简单的递归数据类型之一的教会编码。其他数据类型的编码还会产生一个极其复杂的其他类型的参数多态函数族。还有一些参数多态函数，它们不对应于任何数据类型的教堂编码。

尝试写下所有参数多态函数的列表实际上是一项毫无希望的任务，类似于(由Curry-Howard同构)写下所有数学真理的列表！

另外，是否有某种形式模式将参数多态函数与必须用重载(ad )定义的多态函数分离？

不怎么有意思。在GHC中通过字典实现类型化可以证明，依赖于ad多态性的任何定义都可以转换为使用参数多态性，而不是以系统的、机械的方式。