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



《编程中的类型多态性理论》第349页第5段中,米尔纳说:

对我们来说,程序中存在的多态性是自然产生的。 的原始多态运算符,似乎存在于每个 程序设计语言;这样的运算符是赋值、函数 应用程序、配对和更新以及列表处理运算符。

此描述是否定义了完整的参数化多态函数集(当我们扩展列表处理运算符以表示所有递归数据类型的运算符时(?(+*, ...需要以临时样式定义,对于它们处理的每种类型具有不同的底层实现(。此外,是否有某种形式模式可以将参数化多态函数与必须通过重载(ad hoc(定义的函数分开?

此描述是否定义了完整的参数化多态函数集?

丘奇教导我们,有一个无限丰富的参数多态函数集合。例如:

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

所有的zeroonetwothree都是参数多态函数;它们都是不同的,因为我们可以应用它们的参数,为每个参数给出不同的结果。这只是最简单的递归数据类型之一的 Church 编码。其他数据类型的编码也产生了一个非常复杂的其他类型的参数多态函数系列......并且存在参数化多态函数,它们与任何数据类型的 Church 编码都不对应。

试图写下所有参数多态函数的列表确实是一项无望的任务,类似于(通过库里-霍华德同构(写下所有数学真理的列表!

此外,是否有某种形式模式可以将参数化多态函数与必须通过重载(ad hoc(定义的函数分开?

没有。GHC 中类型类的字典传递实现证明了任何依赖于临时多态性的定义都可以以系统的机械方式转换为使用参数多态性。

相关内容

  • 没有找到相关文章

最新更新