Rank2Types的目的是什么？

Question

Rank2Types的目的是什么？

haskelltypespolymorphismhigher-rank-types

120

我并不是Haskell的专家，所以这可能是一个非常简单的问题。

Rank2Types解决了哪些语言限制？在Haskell中，函数不已经支持多态参数吗？

- Andrey Shchekin

这基本上是从HM类型系统升级到多态λ演算，也称为λ2/System F。请记住，在λ2中，类型推断是不可判定的。 - Poscat

5个回答

124

Haskell中的函数已经支持多态参数了吗？是的，但只支持一阶多态。这意味着，虽然你可以编写一个不使用该扩展就接受不同类型参数的函数，但不能编写一个在同一调用中将其参数用作不同类型的函数。例如，由于在定义f时使用了不同的参数类型，所以以下函数无法进行类型推断：g。

f g = g 1 + g "lala"

请注意，将一个多态函数作为另一个函数的参数传递是完全可能的。因此，类似于map id ["a","b","c"]这样的东西是完全合法的。但该函数只能将其作为单态函数使用。在示例中，map将id用作String -> String类型。当然，您也可以传递具有给定类型的简单单态函数，而不是id。没有rank2types，函数无法要求其参数必须是多态函数，因此也无法将其用作多态函数。

- sepp2k

6

补充一些关于我的回答的内容：考虑 Haskell 函数 f' g x y = g x + g y，它的推断等级-1类型是 forall a r. Num r => (a -> r) -> a -> a -> r。由于 forall a 处于函数箭头之外，调用者必须先为 a 选择一个类型；如果他们选择了 Int，我们得到 f' :: forall r. Num r => (Int -> r) -> Int -> Int -> r，现在我们已经固定了g参数，因此它可以获取 Int 类型的值但不能获取 String 类型的值。如果我们启用了 RankNTypes，我们就可以使用类型注释 forall b c r. Num r => (forall a. a -> r) -> b -> c -> r 来注释 f'。不过我们无法使用它——因为 g 应该是什么呢？ - Luis Casillas

55

Luis Casillas的回答提供了很多关于rank 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 ()

这其实没有任何帮助，因为当我们调用f函数时选择了类型a，并且仅将其特化为Country，然后再次使用恶意代码\_ -> BestAlly。解决方案是使用排名为2的类型：

f :: (forall a . [a] -> a) -> IO ()

现在我们需要传入的函数必须是多态的，所以 \_ -> BestAlly 将无法通过类型检查！事实上，没有任何函数 返回不在给定列表中的元素将通过类型检查（尽管有些进入无限循环或产生错误从而永远不返回的函数会这样做）。

当然，以上是人为制造的情况，但这种技术的一种变化对于使 ST monad 安全至关重要。

- dfeuer

这是否类似于Julia的动态分派？被调用者必须恰好符合所需类型，不能多也不能少。 - user3680029

另一个尝试是ST monad为什么有效？特别是runST，您无法传递属于不同线程状态的值。这些值的列表有点像那个线程吗？它捕获了一些你逃不掉的值... - user3680029

抱歉，当添加BestAlly到列表中时，它无法工作 f :: (forall a. [a] -> a) -> IO() f g = launchMissilesAt $ g [BigEnemy，MediumEnemy，PunyEnemy，BestAlly] 然后 f (_ -> BestAlly) => 无法匹配预期类型'a'与实际类型'Country'...没有提供列表中的BestAlly就可以工作。为什么？ - user3680029

@user3680029 这就是整个意图。你不能使用任何特定的一个；你必须从给定的列表中选择一个。 - dfeuer

右 f 最后起作用了 - 还需要理清思路..谢谢 - user3680029

显示剩余4条评论

22

高阶类型并不像其他答案所说的那么奇特。信不信由你，许多面向对象的语言（包括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＃中。

- Benjamin Hodgson

2

我很想知道是否有其他人写过关于C＃/Java/Blub对高阶类型的支持的文章。如果您，亲爱的读者，知道任何此类资源，请将它们发送给我！ - Benjamin Hodgson

-4

对于熟悉面向对象语言的人来说，高阶函数就是一个期望其参数为另一个通用函数的通用函数。

例如，在TypeScript中，您可以编写：

type WithId<T> = T & { id: number }
type Identifier = <T>(obj: T) => WithId<T>
type Identify = <TObj>(obj: TObj, f: Identifier) => WithId<TObj>

看看通用函数类型Identify如何需要一个类型为Identifier的通用函数？这使得Identify成为一个高阶函数。

- Asad Saeeduddin

这对sepp2k的回答有什么补充？ - dfeuer

@dfeuer在更熟悉Haskell或System F的人中，它阐述了更高级别类型的概念。此外，据我所见，Benjamin Hodgson的回答并不是更高级别类型的实际示例；IEmployee接受单态类型IEmployeeVisitor<T>。类型IEmployeeVisitor已经完全应用。只有当您接受开放式多态类型时，才会出现更高级别的输入。 - Asad Saeeduddin

1

我认为你没有理解霍奇森的观点。Accept具有一阶多态类型，但它是IEmployee的方法，而IEmployee本身是二阶的。如果有人给我一个IEmployee，我可以打开它并在任何类型上使用它的Accept方法。 - dfeuer

1

你的例子也是rank-2的，通过引入Visitee类。一个函数 f :: Visitee e => T e （一旦类的东西被desugared处理）本质上是 f :: (forall r. e -> Visitor e r -> r) -> T e。Haskell 2010使用这样的类让你能够有限制的rank-2多态。 - dfeuer

1

你不能将 forall 从我的示例中移出。我手头没有参考资料，但你可能会在 "Scrap Your Type Classes" 中找到一些相关内容。高阶多态确实可能会引入类型检查问题，但类系统中的有限排序是可以接受的。 - dfeuer

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Luis Casillas · Accepted Answer

"It's hard to understand higher-rank polymorphism unless you study System F directly, because Haskell is designed to hide the details of that from you in the interest of simplicity.

But basically, the rough idea is that polymorphic types don't really have the a -> b form that they do in Haskell; in reality, they look like this, always with explicit quantifiers."

id :: ∀a.a → a
id = Λt.λx:t.x

如果你不知道"∀"符号，它的读音是"for all"; ∀x.dog(x) 的意思是"对于所有的x，x都是一只狗"。 "Λ"是大写的lambda符号，用于抽象类型参数；第二行的意思是id是一个函数，它接受一个类型t，然后返回一个由该类型参数化的函数。

你看，在System F中，你不能直接将这样的函数id应用到一个值上；首先你需要将Λ函数应用到一个类型上，以获得一个λ函数，然后再将其应用到一个值上。例如：

(Λt.λx:t.x) Int 5 = (λx:Int.x) 5
                  = 5

标准Haskell（即Haskell 98和2010）通过不具有任何此类类型量化器、大写希腊字母和类型应用，为您简化了此操作。但是，GHC在分析编译程序时会将它们添加到程序中。我相信这都是编译时的事情，没有运行时开销。

但是Haskell的自动处理意味着它假定“∀”从不出现在函数（“→”）类型的左分支上。Rank2Types和RankNTypes关闭这些限制，并允许您覆盖Haskell的默认规则以插入forall的位置。

为什么要这样做？因为完整的、无限制的System F非常强大，它可以做很多酷炫的事情。例如，可以使用更高级别的类型来实现类型隐藏和模块化。举个例子，考虑以下排名1类型的普通函数：

f :: ∀r.∀a.((a → r) → a → r) → r

要使用f，调用者首先必须选择要用于r和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。这意味着 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，其中a是未知的。对于myObject的客户端来说，它们不知道a的具体类型，但从签名中可以知道，它们将能够应用这两个函数之一，并获得Int或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：对于任何想知道为什么 GHC 中的 ExistentialTypes 使用 forall 的人，我认为原因是因为它在幕后使用了这种技术。