参数多态性和临时多态性

76
我想了解参数多态(比如Java/Scala/C++语言中的泛型类/函数)和Haskell类型系统中“特殊”多态的主要区别。我熟悉第一种语言,但从未使用过Haskell。
更具体地说:
1. 在Java中,类型推断算法与Haskell中的类型推断有何不同?
2. 请举一个例子,说明在Java / Scala中可以编写但在Haskell中无法编写的情况(根据这些平台的模块化特性),反之亦然。

10
参数多态可以忽略正在操作的类型,例如 reverse :: [a] -> [a] 就是这样一种类型。而临时多态函数 sort :: Ord a => [a] -> [a] 需要额外的信息,由类约束 Ord a 来指导。我不确定“临时”的词源,但后一种形式的多态性不是普通 lambda-calculus 的特征。 - vivian
1
@Eliah Java不需要为泛型类显式指定类型。例如,List<T> filter(Function<T>, List<T>)完全不关心T是什么。你的例子是参数多态性和子类型多态性的混合,这引起了协变和逆变。这与临时多态性是两回事。 - user545680
2
@Eliah 是的。你可以将像 Read a => 这样的东西在脑海中翻译成类似于 <? extends Read> 的内容(我不太确定,因为我已经很久没有写 Java 了)。 - fuz
3
只是出于好奇,你为什么想要比较Java的参数多态性和Haskell的特设多态性?将Java的参数多态性与Haskell的参数多态性进行比较,然后将Java的特设多态性与Haskell的特设多态性进行比较,这样不会更有意义吗? - Jörg W Mittag
6
请查看此前的回答:https://dev59.com/CG035IYBdhLWcg3wBLRL#5671329 - Don Stewart
显示剩余3条评论
3个回答

91
根据TAPL,§23.2:
参数多态(...)允许使用变量代替实际类型来“通用”地为单个代码片段编写类型,并在需要时实例化特定类型。参数定义是统一的:它们的所有实例都表现相同。(...)
相比之下,特殊多态性允许多态值在不同类型下展示不同的行为。最常见的特殊多态性例子是重载,它将单个函数符号与许多实现相关联;编译器(或运行时系统,具体取决于重载解析是静态还是动态的)为每个函数应用选择适当的实现,基于参数的类型。

因此,如果您考虑历史的连续阶段,非通用官方Java(也称为J2SE 5.0之前的版本,即2004年9月之前)具有特定的多态性 - 因此您可以重载方法 - 但没有参数化的多态性,因此您无法编写通用方法。当然,之后您都可以做到这两点。

相比之下,自1990年成立以来,Haskell就是参数化多态的,这意味着您可以编写:

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

其中A和B是类型变量,可以实例化为所有类型,没有任何假设。

但是之前并没有提供给特定场景的多态性构造,这意味着您无法编写适用于多个,但不是所有类型的函数。类型类被实现为实现此目标的一种方式。

它们允许您描述一个(类似于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之间的关键区别在于,只有Haskell可以自动进行字典传递:在两种语言中,假设有两个Ord T的实例,比如b0b1,您可以构建一个函数f,它以这些作为参数并生成对于成对类型(b0,b1)的实例,例如使用词典顺序。现在假设您有((“hello”,2),((3,“hi”),5))。在Java中,您必须记住stringint的实例,并传递正确的实例(由四个f应用组成!)才能将between应用于该对象。Haskell可以应用组合性,并找出如何仅通过基础实例和f构造函数构建正确的实例(当然,这也适用于其他构造函数)。


现在,就类型推断而言(这可能应该是一个不同的问题),对于两种语言来说都是不完全的,因为您总是可以编写一个未注释的程序,编译器将无法确定其类型。

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

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

但是,这些语言主要在实践中的类型推断适用范围和给予类型推断结果正确性的重要性方面存在差异。

对于 Haskell,推断适用于所有“非高度多态”的术语,并且会认真努力基于已知算法的发布扩展返回可靠结果:
  • 在其核心,Haskell的推断基于Hindley-Milner,当推断应用程序类型时,它会立即给出完整的结果。类型变量(例如上面示例中的AB)只能实例化为非多态类型(我在简化,但这本质上是您可以在例如Ocaml中找到的ML风格的多态性)。
  • 最近的GHC将确保类型注释可能仅需要用于具有非Damas-Milner类型的let绑定或λ抽象(我在简化,但这本质上是您可以在例如Ocaml中找到的ML风格的多态性)
  • Haskell试图保持相对接近这个可推断的核心,即使是在其最复杂的扩展(例如GADTs)中也是如此。无论如何,提议的扩展几乎总是在带有扩展类型推断正确性证明的论文中提出。
对于Java,类型推断的应用方式非常有限
在Java 5发布之前,Java中没有类型推断。根据Java语言文化,每个变量、方法和动态分配的对象的类型必须由程序员显式声明。当泛型(由类型参数化的类和方法)在Java 5中引入时,语言保留了这种要求,适用于变量、方法和分配。但是,多态方法(由类型参数化)的引入决定了以下两种情况:(i) 程序员在每个多态方法调用站点提供方法类型参数;或者(ii) 语言支持推断方法类型参数。为避免为程序员创建额外的文书负担,Java 5的设计者选择执行类型推断以确定类型参数的多态方法调用。(source,我强调)

推理算法本质上是GJ的算法,但是增加了一些有点 笨拙的通配符作为事后想法的补充(请注意,我不知道J2SE 6.0中可能进行的更正)。在方法论上的巨大差异在于Java的推理是局部的,也就是说,表达式的推断类型仅取决于从类型系统生成的约束和其子表达式的类型,而不取决于上下文。

请注意,关于不完整且有时不准确的类型推断的立场相对轻松。根据规范

还要注意,类型推断不会以任何方式影响音度。如果推断出来的类型是荒谬的,则调用将产生类型错误。应将类型推断算法视为一种启发式算法,旨在在实践中表现良好。如果它未能推断出所需的结果,则可以改用显式类型参数。


40

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

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

我们不关心列表中元素的类型,只关心它们的数量。

临时多态(又名方法重载)意味着我们将根据参数的类型使用不同的实现方式。

下面是Haskell中的一个例子。假设我们想定义一个名为makeBreakfast的函数。

如果输入参数是Eggs,我希望makeBreakfast返回如何制作鸡蛋的消息。

如果输入参数是Pancakes,我希望makeBreakfast返回如何制作煎饼的消息。

我们将创建一个名为BreakfastFood的类型类,该类型类实现了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"

根据约翰·米切尔的《编程语言概念》,参数多态和重载(也称为特殊多态)之间的关键区别在于,参数多态函数使用一种算法来操作许多不同类型的参数,而重载函数可能会针对每种参数类型使用不同的算法。



0

关于参数多态和特定多态的完整讨论,以及它们在Haskell和Java中的可用程度,需要较长的篇幅;然而,您具体的问题可以更简单地解决:

Java中类型推断的算法与Haskell中的类型推断有何不同?

据我所知,Java不进行类型推断。因此,区别在于Haskell进行了类型推断。

请给我一个例子,说明某些情况下可以在Java / Scala中编写但无法在Haskell中编写(根据这些平台的模块化功能),反之亦然。

Haskell可以做到而Java无法做到的一个非常简单的例子是定义maxBound :: Bounded a => a。我不了解足够的Java来指出Haskell无法做到的事情。


2
Daniel,感谢您的回复。据我所知,Java允许类型推断(类型参数的推断),但是推断的范围非常有限,而Scala提供了类似的类型系统(略微更广泛,但相似)和更广泛的推断范围。因此,在类型推断的上下文中可以将Java / Scala与Haskell进行比较。例如,您在Haskell中的示例也可以在Java中编写:<A extends Bounded> A maxBound(); - Ilya Lakhin
2
@Eliah,虽然你可以在Java中声明这样的方法,但我怀疑你实际上无法实现它的主体(除非使用return null;)。不过,在Scala中使用隐式参数是可能的。 - Rotsor
1
这不是在Java中定义它的方式吗: interface Bounded<A> { A maxBound(); }class BoundedInt implements Bounded { private final int bound; public BoundedInt(int bound) { this.bound = bound; } public Integer maxBound() { return bound; } } 抱歉格式有点乱。虽然冗长,但它似乎正是Haskell中Bounded所做的事情。 - xpmatteo

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接