我不是很精通 Haskell，所以这可能是一个非常简单的问题。
Rank2Types解决了哪些语言限制？Haskell 中的函数不是已经支持多态参数了吗？
问问题
14267 次
5 回答
175
除非您直接研究System F ，否则很难理解高级多态性，因为为了简单起见，Haskell 旨在向您隐藏其中的细节。
但基本上，粗略的想法是多态类型并不真正具有a -> b它们在 Haskell 中的形式。实际上，它们看起来像这样，总是带有明确的量词：
id :: ∀a.a → a
id = Λt.λx:t.x
如果你不知道“∀”符号，读作“for all”；∀x.dog(x)意思是“对于所有 x，x 是一条狗。” “Λ”是大写的 lambda，用于抽象类型参数；第二行说的是 id 是一个接受 typet的函数，然后返回一个由该类型参数化的函数。
你看，在 System F 中，你不能立即将这样的函数应用于id一个值；首先，您需要将 Λ 函数应用于类型，以便获得应用于值的 λ 函数。例如：
(Λt.λx:t.x) Int 5 = (λx:Int.x) 5
= 5
标准 Haskell（即 Haskell 98 和 2010）通过没有任何这些类型量词、大写 lambda 和类型应用程序为您简化了这一点，但 GHC 在分析程序以进行编译时将它们放在幕后。（我相信这都是编译时的东西，没有运行时开销。）
但是 Haskell 对此的自动处理意味着它假定“∀”永远不会出现在函数（“→”）类型的左侧分支上。 Rank2Types并RankNTypes关闭这些限制并允许您覆盖 Haskell 关于 where to insert 的默认规则forall。
你为什么想做这个？因为完整的、不受限制的 System F 非常强大，它可以做很多很酷的事情。例如，类型隐藏和模块化可以使用更高级别的类型来实现。以以下 rank-1 类型的普通旧函数为例（设置场景）：
f :: ∀r.∀a.((a → r) → a → r) → r
要使用f，调用者首先必须选择用于rand的类型a，然后提供结果类型的参数。所以你可以选择r = Int和a = String：
f Int String :: ((String → Int) → String → Int) → Int
但现在将其与以下更高级别的类型进行比较：
f' :: ∀r.(∀a.(a → r) → a → r) → r
这种类型的功能如何工作？好吧，要使用它，首先您指定要使用的类型r。假设我们选择Int：
f' Int :: (∀a.(a → Int) → a → Int) → Int
但是现在在∀a函数箭头里面，所以你不能选择使用什么类型a；您必须应用f' Int适当类型的 Λ 函数。这意味着gets的实现f'选择使用什么类型a，而不是f'. 相反，如果没有更高级别的类型，调用者总是选择类型。
这有什么用？好吧，实际上对于很多事情，但一个想法是，您可以使用它来建模诸如面向对象编程之类的事情，其中“对象”将一些隐藏数据与一些处理隐藏数据的方法捆绑在一起。例如，一个具有两种方法的对象——一个返回一个Int，另一个返回一个String，可以用这种类型实现：
myObject :: ∀r.(∀a.(a → Int, a -> String) → a → r) → r
这是如何运作的？该对象被实现为具有一些隐藏类型的内部数据的函数a。要实际使用该对象，它的客户端会传入一个“回调”函数，该对象将使用这两种方法调用该函数。例如：
myObject String (Λa. λ(length, name):(a → Int, a → String). λobjData:a. name objData)
基本上，我们在这里调用对象的第二种方法，即类型a → String为 unknown的方法a。好吧，myObject客户不知道；但是这些客户端确实从签名中知道，他们将能够对其应用这两个函数中的任何一个，并获得 anInt或 a String。
对于一个实际的 Haskell 示例，下面是我自学时编写的代码RankNTypes。这实现了一个名为的类型，它将某个隐藏类型的值与其类实例ShowBox捆绑在一起。Show请注意，在底部的示例中，我创建了一个列表，ShowBox其中第一个元素由数字组成，第二个元素由字符串组成。由于这些类型是通过使用更高级别的类型来隐藏的，因此这不会违反类型检查。
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ImpredicativeTypes #-}
type ShowBox = forall b. (forall a. Show a => a -> b) -> b
mkShowBox :: Show a => a -> ShowBox
mkShowBox x = \k -> k x
-- | This is the key function for using a 'ShowBox'. You pass in
-- a function @k@ that will be applied to the contents of the
-- ShowBox. But you don't pick the type of @k@'s argument--the
-- ShowBox does. However, it's restricted to picking a type that
-- implements @Show@, so you know that whatever type it picks, you
-- can use the 'show' function.
runShowBox :: forall b. (forall a. Show a => a -> b) -> ShowBox -> b
-- Expanded type:
--
-- runShowBox
-- :: forall b. (forall a. Show a => a -> b)
-- -> (forall b. (forall a. Show a => a -> b) -> b)
-- -> b
--
runShowBox k box = box k
example :: [ShowBox]
-- example :: [ShowBox] expands to this:
--
-- example :: [forall b. (forall a. Show a => a -> b) -> b]
--
-- Without the annotation the compiler infers the following, which
-- breaks in the definition of 'result' below:
--
-- example :: forall b. [(forall a. Show a => a -> b) -> b]
--
example = [mkShowBox 5, mkShowBox "foo"]
result :: [String]
result = map (runShowBox show) example
PS：对于阅读本文的任何人，如果想知道ExistentialTypesGHC 是如何使用forall的，我相信原因是因为它在幕后使用了这种技术。
于 2012-08-20T07:11:44.567 回答
121
Haskell 中的函数不是已经支持多态参数了吗？
他们这样做了，但只有等级 1。这意味着虽然您可以编写一个在没有此扩展的情况下采用不同类型参数的函数，但您不能编写一个在同一调用中使用其参数作为不同类型的函数。
例如，如果没有此扩展名，则无法键入以下函数，因为g在 的定义中与不同的参数类型一起使用f：
f g = g 1 + g "lala"
请注意，完全可以将多态函数作为参数传递给另一个函数。所以类似的东西map id ["a","b","c"]是完全合法的。但是该函数只能将其用作单态。在示例中map使用id好像它有 type String -> String。当然，您也可以传递给定类型的简单单态函数，而不是id. 如果没有 rank2types，函数就无法要求其参数必须是多态函数，因此也无法将其用作多态函数。
于 2012-08-20T03:14:32.387 回答
52
Luis Casillas 的回答提供了很多关于 2 级类型意味着什么的重要信息，但我将仅扩展他未涵盖的一点。要求参数是多态的不仅允许它与多种类型一起使用；它还限制了该函数可以使用其参数做什么以及它如何产生结果。也就是说，它给调用者较少的灵活性。你为什么想这么做？我将从一个简单的例子开始：
假设我们有一个数据类型
data Country = BigEnemy | MediumEnemy | PunyEnemy | TradePartner | Ally | BestAlly
我们想写一个函数
f g = launchMissilesAt $ g [BigEnemy, MediumEnemy, PunyEnemy]
它采用一个函数，该函数应该选择它给出的列表中的一个元素，并返回一个IO向该目标发射导弹的动作。我们可以给出f一个简单的类型：
f :: ([Country] -> Country) -> IO ()
问题是我们可能会意外运行
f (\_ -> BestAlly)
然后我们就有大麻烦了！给出f等级 1 的多态类型
f :: ([a] -> a) -> IO ()
根本没有帮助，因为我们a在调用时选择了类型f，我们只是将其专门用于Country并再次使用我们的恶意软件\_ -> BestAlly。解决方案是使用等级 2 类型：
f :: (forall a . [a] -> a) -> IO ()
现在我们传入的函数需要是多态的，所以\_ -> BestAlly不会进行类型检查！事实上，返回不在给定列表中的元素的任何函数都不会进行类型检查（尽管某些进入无限循环或产生错误并因此永远不会返回的函数会这样做）。
当然，以上是人为设计的，但是这种技术的变体是使STmonad 安全的关键。
于 2014-07-12T21:57:10.160 回答
20
更高级别的类型并不像其他答案所表明的那样奇特。信不信由你，许多面向对象的语言（包括 Java 和 C#！）都具有它们。（当然，那些社区中没有人以“高级类型”这个听起来很吓人的名字认识他们。）
我要给出的示例是访问者模式的教科书实现，我在日常工作中一直使用它。此答案并非旨在介绍访问者模式；这些知识在其他地方很容易 获得 。
在这个愚蠢的虚构 HR 应用程序中，我们希望对可能是全职长期员工或临时承包商的员工进行操作。我首选的访问者模式变体（实际上是与 相关的变体RankNTypes）参数化了访问者的返回类型。
interface IEmployeeVisitor<T>
{
T Visit(PermanentEmployee e);
T Visit(Contractor c);
}
class XmlVisitor : IEmployeeVisitor<string> { /* ... */ }
class PaymentCalculator : IEmployeeVisitor<int> { /* ... */ }
关键是许多具有不同返回类型的访问者都可以对相同的数据进行操作。这意味着不能对应该是IEmployee什么发表意见。T
interface IEmployee
{
T Accept<T>(IEmployeeVisitor<T> v);
}
class PermanentEmployee : IEmployee
{
// ...
public T Accept<T>(IEmployeeVisitor<T> v)
{
return v.Visit(this);
}
}
class Contractor : IEmployee
{
// ...
public T Accept<T>(IEmployeeVisitor<T> v)
{
return v.Visit(this);
}
}
我想提请您注意这些类型。请注意，它IEmployeeVisitor普遍量化了它的返回类型，而在它的方法IEmployee内部量化它Accept- 也就是说，在更高的等级。从 C# 到 Haskell 的翻译很笨拙：
data IEmployeeVisitor r = IEmployeeVisitor {
visitPermanent :: PermanentEmployee -> r,
visitContractor :: Contractor -> r
}
newtype IEmployee = IEmployee {
accept :: forall r. IEmployeeVisitor r -> r
}
所以你有它。当您编写包含泛型方法的类型时，更高级别的类型会出现在 C# 中。
于 2016-01-06T00:45:47.627 回答
-4
For those familiar with object oriented languages, a higher-rank function is simply a generic function that expects as its argument another generic function.
E.g. in TypeScript you could write:
type WithId<T> = T & { id: number }
type Identifier = <T>(obj: T) => WithId<T>
type Identify = <TObj>(obj: TObj, f: Identifier) => WithId<TObj>
See how the generic function type Identify demands a generic function of the type Identifier? This makes Identify a higher-rank function.
于 2017-07-27T16:31:31.560 回答