参数多态性与Ad-hoc多态性

Question

我想了解参数多态性之间的关键区别,例如Java/Scala/C++语言中泛型类/函数的多态性和Haskell类型系统中的"ad-hoc"多态性.我熟悉第一种语言,但我从未使用过Haskell.

更确切地说:

1. 如何在Java中的类型推断算法与Haskell中的类型推断不同？
2. 请给我一个例子,说明可以用Java/Scala编写的东西,但不能用Haskell编写(根据这些平台的模块化特性),反之亦然.

提前致谢.

Answer 1

根据TAPL,§23.2:

参数多态(...)允许单个代码"通用",使用变量代替实际类型,然后根据需要使用特定类型进行实例化.参数定义是统一的:它们的所有实例都表现相同.(......)

相反,Ad-hoc多态性允许多态值在不同类型"观察"时表现出不同的行为.ad-hoc多态的最常见的例子是重载,它将单个函数符号与许多实现相关联; 编译器(或运行时系统,取决于重载分辨率是静态还是动态)根据参数的类型为函数的每个应用程序选择适当的实现.

因此,如果你考虑历史的连续阶段,非通用官方Java(也称为J2SE 5.0之前,2004年9月)具有ad-hoc多态性 - 所以你可以重载一个方法 - 但不是参数多态,所以你不能'吨写一个通用的方法.当然,你可以做到这两点.

相比之下,从1990年开始,Haskell就具有参数多态性,这意味着你可以写:

swap :: (A; B) -> (B; A)
swap (x; y) = (y; x)

其中A和B是类型变量,可以实例化为所有类型,无需假设.

但是没有预先存在的构造给出ad-hoc多态,它打算让你编写适用于几种但不是所有类型的函数.实现类型类是实现此目标的一种方式.

它们允许您描述一个类(类似于Java接口),给出您希望为泛型类型实现的函数的类型签名.然后,您可以注册与此类匹配的一些(并且希望是几个)实例.在此期间,您可以编写一个通用方法,例如:

between :: (Ord a)  a -> a -> a -> Bool
between x y z = x ? y ^ y ? z

其中Ord是定义函数的类(_ ? _).在使用时,(between "abc" "d" "ghi")被静态解析选择正确的实例字符串(而不是如整数) -也就是在那一刻(Java的)方法重载会.

您可以使用有界通配符在Java中执行类似的操作.但是,在这一方面Haskell和Java之间的主要区别是,只有哈斯克尔可以自动完成字典的传球:在两种语言中,给出的两个实例Ord T,说b0和b1,您可以建立一个功能f是需要这些作为参数,并产生实例对类型(b0, b1),使用,例如,词典顺序.现在说你得到了(("hello", 2), ((3, "hi"), 5)).在Java中,你必须记住的实例为string和int,并通过正确的实例(由四个应用程序f才能申请!)between到该对象.Haskell可以应用组合性,并找出如何仅在地面实例和f构造函数的情况下构建正确的实例(当然,这扩展到其他构造函数).

现在,就类型推断而言(这应该是一个独特的问题),对于这两种语言而言它是不完整的,因为你总是可以编写一个未注释的程序,编译器将无法确定该程序类型.

1. 对于Haskell来说,这是因为它具有不可预测的(也就是一流的)多态性,其类型推断是不可判定的.请注意,在这一点上,Java仅限于一阶多态(Scala扩展的东西).

2. 对于Java,这是因为它支持逆变子类型.

但是这些语言主要在类型推理在实践中应用的程序语句的范围以及对类型推断结果的正确性的重要性方面存在差异.

1. 对于Haskell,推理适用于所有"非高度多态"术语,并根据已知算法的已发布扩展,努力返回声音结果:

   • 在其核心,Haskell的推论是基于辛德米尔纳尽快,它给你完整的结果作为infering的应用程序的类型时,类型变量(例如A与B上面的例子),可以只实例化的非多态性类型(我正在简化,但这实际上是你可以在例如Ocaml中找到的ML风格的多态性.).
   • 最近的GHC将确保只有具有非Damas-Milner类型的let-binding或λ-abstraction才需要类型注释.
   • Haskell试图保持相对接近这个可推断的核心,即使是最毛茸茸的扩展(例如GADT).无论如何,提议的扩展几乎总是出现在一篇论文中,证明了扩展类型推断的正确性.

2. 对于Java,类型推断无论如何都适用于更有限的方式:

   在Java 5发布之前,Java中没有类型推断.根据Java语言文化,程序员必须显式声明每个变量,方法和动态分配对象的类型.当在Java 5中引入泛型(按类型参数化的类和方法)时,该语言保留了对变量,方法和分配的这一要求.但是多态方法的引入(按类型参数化)决定了(i)程序员在每个多态方法调用站点提供方法类型参数或(ii)语言支持方法类型参数的推断.为避免给程序员带来额外的文书负担,Java 5的设计者选择执行类型推断来确定多态方法调用的类型参数.(来源,强调我的)

   该推理算法基本上是GJ的,但有几分 缺憾此外通配符作为一种事后(请注意,我不是最新的在J2SE 6.0所做的可能修正,虽然).方法中的大概念差异在于Java的推理是 本地的,在某种意义上,表达式的推断类型仅取决于从类型系统生成的约束及其子表达式的类型,而不取决于上下文.

   请注意,关于不完整和有时不正确的类型推断的聚会线是相对悠闲的.根据规范:

   另请注意,类型推断不会以任何方式影响健全性.如果推断的类型是无意义的,则调用将产生类型错误.类型推理算法应被视为一种启发式算法,旨在在实践中很好地实现.如果它无法推断出期望的结果,则可以使用显式类型参数.

Answer 2

参数多态意味着,我们不关心类型,我们将为任何类型实现相同的功能.例如,在Haskell中:

length :: [a] -> Int
length [] = 0          
length (x:xs) = 1 + length xs

我们不关心列表中元素的类型,我们只关心有多少.

然而,Ad-hoc多态(也就是方法重载)意味着我们将根据参数的类型使用不同的实现.

这是Haskell中的一个例子.假设我们要定义一个名为的函数makeBreakfast.

如果输入参数是Eggs,我想makeBreakfast返回一个关于如何制作蛋的消息.

如果输入参数是Pancakes,我想makeBreakfast返回一个关于如何制作煎饼的消息.

我们将创建一个称为BreakfastFood实现该makeBreakfast函数的类型类.makeBreakfast根据输入的类型,执行情况会有所不同makeBreakfast.

class BreakfastFood food where
  makeBreakfast :: food -> String

instance BreakfastFood Eggs where
  makeBreakfast = "First crack 'em, then fry 'em"

instance BreakfastFood Toast where
  makeBreakfast = "Put bread in the toaster until brown"

根据约翰米切尔的编程语言概念,

参数多态和重载(又称ad-hoc多态)之间的关键区别在于参数多态函数使用一种算法来操作许多不同类型的参数,而重载函数可以对每种类型的参数使用不同的算法.