Was ist der Zweck der Rank2Types?

Es ist schwer zu verstehen, höheren Rang Polymorphismus, es sei denn, Sie studieren System F direkt, denn Haskell ist entworfen, um zu verbergen die details der von Ihnen im Interesse der Einfachheit.

Aber im Grunde genommen, die grobe Idee ist, dass polymorphe Typen haben nicht wirklich die a -> b form, dass Sie in Haskell; in Wirklichkeit sehen Sie so wie hier, immer mit expliziten Quantoren:

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

Wenn Sie nicht wissen, die " ∀ " - symbol, es ist zu Lesen als "für alle"; ∀x.dog(x) bedeutet "für alle x, x ist ein Hund." "Λ" ist die Hauptstadt lambda-Ausdruck, der verwendet, für die Abstraktion über Typ-Parameter; was die zweite Zeile sagt, dass id ist eine Funktion, eine Art t, und gibt dann eine Funktion, parametrisiert durch, der Typ.

Sehen Sie, System F, Sie können nicht nur eine Funktion wie, dass id auf einen Wert gleich; zuerst müssen Sie auf anwenden, um die Λ-Funktion auf einen Typ, um eine λ-Funktion, die Sie auf einen Wert. So zum Beispiel:

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

Standard-Haskell (D. H., Haskell 98 und 2010) vereinfacht dies für Sie nicht mit jeder dieser Art Quantoren -, Kapital-Lambda-Ausdrücke und Typ-Anwendungen, aber hinter den kulissen GHC setzt Sie ein, wenn es analysiert das Programm für die Zusammenstellung. (Dies ist alle compile-Zeit-Zeug, glaube ich, keine Laufzeit-overhead.)

Aber Haskell ist die automatische Handhabung von das heißt, es wird davon ausgegangen, dass "∀" erscheint nie auf der linken hand Zweig einer Funktion ("→") geben. Rank2Types und RankNTypes schalten Sie diese Einschränkungen und erlauben Sie das überschreiben Haskell die default-Regeln für die, wo zum einfügen forall.

Warum würden Sie wollen, dies zu tun? Weil die volle, uneingeschränkte System F ist hella mächtig, und es kann eine Menge Coole Sachen. Geben Sie beispielsweise ausblenden und Modularität umgesetzt werden können, mit höheren Rang-Typen. Nehmen Sie zum Beispiel eine einfache alte Funktion der folgenden Rang-1-Typ (in Szene gesetzt):

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

Verwenden f, der Anrufer muss zunächst auswählen, welche Art zu verwenden, für r und a, liefern dann ein argument des resultierenden Typs. So konnte man wählen r = Int und a = String:

f Int String :: ((String → Int) → String → Int) → Int

Aber jetzt vergleichen Sie das mit den folgenden höheren Rang Typ:

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

Wie sieht eine Funktion dieser Art Arbeit? Naja, zu verwenden, müssen Sie zuerst bestimmen Sie, welche Art zu verwenden, für r. Sagen wir Holen Int:

f' Int :: (∀a.(a → Int) → a → Int) → Int

Aber jetzt die ∀a ist innen die Funktion Pfeil, so können Sie nicht auswählen, welche Art zu verwenden, für a; Sie müssen f' Int zu einem Λ-Funktion des entsprechenden Typs. Dies bedeutet, dass die Umsetzung der f' bekommt zu wählen, welche Art zu verwenden, für a nicht den Aufrufer der f'. Ohne höheren Rang Typen, im Gegenteil, der Anrufer wählt immer die Typen.

Was ist dieser nützlich? Gut, für viele Dinge, eigentlich, aber eine Idee ist es, dass Sie können mit diesem Modell Dinge wie Objekt-orientierte Programmierung, wo die "Objekte" - bundle einige versteckte Daten zusammen mit einigen Methoden, die auf die versteckten Daten. So zum Beispiel ein Objekt mit zwei Methoden—eine, gibt eine Int und ein anderes, das gibt eine String, umgesetzt werden kann, die mit dieser Art:

myObject :: ∀r.(∀a.(a → Int, a -> String) → a → r) → r

Wie funktioniert das? Das Objekt ist implementiert als eine Funktion, die einige interne Daten von versteckten Typ a. Um tatsächlich mit dem Objekt, seinen Kunden eine "callback" - Funktion, die das Objekt aufrufen, mit den zwei Methoden. Zum Beispiel:

myObject String (Λa. λ(length, name):(a → Int, a → String). λobjData:a. name objData)

Hier sind wir, im Grunde, in dem das Objekt die zweite Methode, deren Typ ist a → String für eine unbekannte a. Gut, unbekannt myObject's Kunden, aber diese Kunden wissen, von der Unterschrift, dass Sie werde in der Lage sein, gelten entweder die beiden Funktionen, und erhalten Sie entweder eine Int oder eine String.

Für eine tatsächliche Haskell Beispiel unten ist der code, den ich schrieb, als ich mir selbst beigebracht RankNTypes. Diese implementiert einen Typ namens ShowBox die bundles, die zusammen einen Wert von einigen versteckten Typ zusammen mit seinen Show Instanz der Klasse. Beachten Sie, dass im Beispiel unten habe ich eine Liste machen ShowBox dessen erstes element wurde aus einer Zahl und die zweite aus einem string. Da die Typen werden ausgeblendet, indem Sie mit der höheren rank-Typen, diese nicht gegen die überprüfung von Typ.

{ -# 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: für jemand der Lektüre dieses wer gefragt, wie kommen ExistentialTypes im GHC verwendet forall ich glaube, der Grund ist, weil es mit dieser Art von Technik hinter den kulissen.

Höheren Rang Typen sind nicht so exotisch wie die anderen Antworten gemacht. Ob Sie es glauben oder nicht, viele objektorientierte Sprachen (wie Java und C#!) verfügen Sie. (Natürlich, niemand in diesen Gemeinden kennt Sie von den unheimlich klingenden Namen "higher-rank-Typen".)

Beispiel werde ich Ihnen ein lehrbuch Umsetzung des Visitor-pattern, welches ich die ganze Zeit in meiner täglichen Arbeit. Diese Antwort ist nicht gedacht als eine Einführung in das Besucher-Muster; dieses wissen ist leicht verfügbar anderswo.

In diesem albern imaginären HR-Anwendung, die wir wollen, zu arbeiten auf Mitarbeiter, die vielleicht Vollzeit-dauerstellen oder temporäre Auftragnehmer. Meine bevorzugte Variante des Visitor-pattern (und zwar eine, die relevant ist, um RankNTypes) parameterises die Besucher zurück geben.

interface IEmployeeVisitor<T>
{
    T Visit(PermanentEmployee e);
    T Visit(Contractor c);
}

class XmlVisitor : IEmployeeVisitor<string> { /* ... */ }
class PaymentCalculator : IEmployeeVisitor<int> { /* ... */ }

Der Punkt ist, dass eine Reihe von Besuchern mit unterschiedlichen Rückgabetypen können alle auf denselben Daten arbeiten. Dies bedeutet IEmployee muss Sie äußern keine Meinung, was T sein sollte.

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);
    }
}

Möchte ich Ihre Aufmerksamkeit auf den Typen. Beachten Sie, dass IEmployeeVisitor universell quantifiziert seiner Rückkehr geben, in der Erwägung, dass IEmployee quantifiziert, die es innerhalb seiner Accept - Methode - das heißt, zu einem höheren Rang. Übersetzung clunkily von C# Haskell:

data IEmployeeVisitor r = IEmployeeVisitor {
    visitPermanent :: PermanentEmployee -> r,
    visitContractor :: Contractor -> r
}

newtype IEmployee = IEmployee {
    accept :: forall r. IEmployeeVisitor r -> r
}

So dort haben Sie es. Höherer Rang-Typen zeigen, bis in C#, wenn Sie schreiben Typen mit generischen Methoden.

Für diejenigen, die vertraut mit objektorientierten Sprachen, mit einer höheren Rang-Funktion ist einfach eine generische Funktion, erwartet als argument eine weitere generische Funktion.

E. g. in Maschinenschrift, könnten Sie schreiben:

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

Sehen, wie die generische Funktion Typ Identify Anforderungen einer generischen Funktion der Art Identifier? Dies macht Identify einen höheren Rang-Funktion.