Wie soll der allgemeine Typ einer "Lemma" -Funktion verstanden werden?

Question

Vielleicht ist das eine dumme Frage. Hier ist ein Zitat aus the Hasochism paper:

Ein Ansatz zur Lösung dieses Problems ist durch parametrisierte Gleichungen Lemmata, gegeben zu codieren, wie Haskell Funktionen. Im Allgemeinen sind solche Lemmata können als Funktionen des Typs codiert werden:

∀ x1 ... xn. Natty x1 → ... → Natty xn → ((l ~ r) ⇒ t) → t 

Ich dachte, ich verstanden RankNTypes, aber ich kann nicht Sinn des letzten Teils dieses Satzes machen. Ich lese es formlos als "gegeben einen Begriff, der l ~ r erfordert, diesen Begriff zurückgeben". Ich bin mir sicher, dass diese Interpretation falsch ist, weil sie zu einer Zirkularität zu führen scheint: Wir wissen nicht bis zum Abschluss des Beweises selbst, wie also kann ich davon ausgehen, dass ich als Beweisannahme einen Begriff vorschlage, der das erfordert ?

ich Beweis eine Gleichheit erwartet hätte eine Art mehr wie diese haben:

Natty x1 → ... → Natty xn → l :~: r 

Informell „ein Bündel von Natty s gegeben, einen Beweis zurückgeben, daß die Sätze l und r gleich sind“ (mit GHC's Data.Type.Equality). Dies ist für mich viel sinnvoller und scheint sich an dem anzupassen, was Sie in anderen abhängig typisierten Systemen sagen würden. Ich schätze, es ist gleichbedeutend mit der Version in der Zeitung, aber ich bemühe mich, die beiden Versionen mental wegzuräumen.

Kurz gesagt, ich bin verwirrt. Ich habe das Gefühl, dass mir eine wichtige Erkenntnis fehlt. Wie soll ich den Typ ((l ~ r) => t) -> t lesen?

Answer 1

ich es als gerade lese „gegeben ein Begriff, der l ~ r erfordert, bringe diese Begriff“

It „ein Begriff, dessen Art gegeben hat enthält l, kehren diesen Begriff mit allen l s ersetzt werden von r s in der Art "(oder in der anderen Richtung r -> l). Es ist ein sehr netter Trick, mit dem Sie alle cong, trans, subst und ähnliche Sachen an GHC delegieren können. Hier

ein Beispiel:

{-# LANGUAGE GADTs, DataKinds, PolyKinds, TypeFamilies, TypeOperators, RankNTypes #-} 

data Nat = Z | S Nat 

data Natty n where 
    Zy :: Natty Z 
    Sy :: Natty n -> Natty (S n) 

data Vec a n where 
    Nil :: Vec a Z 
    Cons :: a -> Vec a n -> Vec a (S n) 

type family (n :: Nat) :+ (m :: Nat) :: Nat where 
    Z  :+ m = m 
    (S n) :+ m = S (n :+ m) 

assoc :: Natty n -> Natty m -> Natty p -> (((n :+ m) :+ p) ~ (n :+ (m :+ p)) => t) -> t 
assoc Zy  my py t = t 
assoc (Sy ny) my py t = assoc ny my py t 

coerce :: Natty n -> Natty m -> Natty p -> Vec a ((n :+ m) :+ p) -> Vec a (n :+ (m :+ p)) 
coerce ny my py xs = assoc ny my py xs 

UPDATE

Es ist lehrreich zu spezialisieren assoc:

assoc' :: Natty n -> Natty m -> Natty p -> 
      (((n :+ m) :+ p) ~ (n :+ (m :+ p)) => Vec a (n :+ (m :+ p))) 
               -> Vec a (n :+ (m :+ p)) 
assoc' Zy  my py t = t 
assoc' (Sy ny) my py t = assoc ny my py t 

coerce' :: Natty n -> Natty m -> Natty p -> Vec a ((n :+ m) :+ p) -> Vec a (n :+ (m :+ p)) 
coerce' ny my py xs = assoc' ny my py xs 

Daniel Wagner erklärt, was in den Kommentaren los ist:

Oder, um es anders auszudrücken, können Sie lesen ((l ~ r) => t) -> t als "gegeben ein Begriff, der gut eingegeben ist, vorausgesetzt, dass l ~ r denselben Ausdruck zurückgeben aus einem Kontext, in dem wir bewiesen haben, dass angenommen wurde ".

Lassen Sie uns die Prüfungsteil erarbeiten.

Im assoc' Zy my py t = t Fall n gleich Zy und daher haben wir

((Zy :+ m) :+ p) ~ (Zy :+ (m :+ p)) 

die

(m :+ p) ~ (m :+ p) 

Dies ist eindeutig Identität

reduziert und somit können wir diese Annahme entladen und t zurückzukehren.

Bei jedem rekursiven Schritt halten wir die

((n :+ m) :+ p) ~ (n :+ (m :+ p)) 

Gleichung. Also, wenn die Gleichung assoc' (Sy ny) my py t = assoc ny my py t

wird

((Sy n :+ m) :+ p) ~ (Sy n :+ (m :+ p)) 

, die reduziert sich auf

Sy ((n :+ m) :+ p) ~ Sy (n :+ (m :+ p)) 

aufgrund der Definition von (:+). Und da Konstrukteure injektiv sind

constructors_are_injective :: S n ~ S m => Vec a n -> Vec a m 
constructors_are_injective xs = xs 

wird die Gleichung

((n :+ m) :+ p) ~ (n :+ (m :+ p)) 

und wir können assoc' rekursiv aufrufen.

schließlich in dem Aufruf von coerce' diese beiden Begriffe vereinigt:

1. ((n :+ m) :+ p) ~ (n :+ (m :+ p)) => Vec a (n :+ (m :+ p)) 
2.          Vec a ((n :+ m) :+ p) 

Klar Vec a ((n :+ m) :+ p)Vec a (n :+ (m :+ p)) unter der Annahme ist, dass ((n :+ m) :+ p) ~ (n :+ (m :+ p)).

Answer 2

ich eine Gleichheit erwartet hätte Beweis eine Art mehr wie diese haben:

Natty x1 → ... → Natty xn → l :~: r 

, dass eine sinnvolle Alternative ist. In der Tat ist es logisch äquivalent zu dem in dem Hasochism Papier:

{-# LANGUAGE GADTs, RankNTypes, TypeOperators, ScopedTypeVariables #-} 
module Hasochism where 

data l :~: r where 
    Refl :: l :~: l 

type Hasoc l r = forall t. (l ~ r => t) -> t 

lemma1 :: forall l r. Hasoc l r -> l :~: r 
lemma1 h = h Refl 

lemma2 :: forall l r. l :~: r -> Hasoc l r 
lemma2 Refl t = t 

In einem gewissen Sinne ist eine Hasoc l r imprädikative Codierung des Constraint l ~ r.

Die Hasochistische Variante ist etwas einfacher zu verwenden als die :~:, in der, sobald Sie z.

type family A a 
-- ... 
proof1 :: Proxy a -> Hasoc a (A a) 
proof1 _ = -- ... 

können Sie es einfach verwenden, wie in

use1 :: forall a. [a] -> [A a] 
use1 t = proof1 (Proxy :: Proxy a) t 

Stattdessen mit

proof2 :: Proxy a -> a :~: A a 
proof2 _ = -- ... 

müssten Sie

use2 :: forall a. [a] -> [A a] 
use2 t = case proof2 (Proxy :: Proxy a) of Refl -> t 

Answer 3

Wir haben einige hervorragende Antworten hatte, aber Als Täter dachte ich, ich würde weggehen einige Bemerkungen.

Ja, es gibt mehrere gleichwertige Darstellungen dieser Lemmas. Die Präsentation, die ich verwende, ist eine davon, und die Wahl ist größtenteils eine pragmatische. In diesen Tagen (in einer neueren Code-Basis), gehe ich so weit definieren

-- Holds :: Constraint -> * 
type Holds c = forall t . (c => t) -> t 

Dies ist ein Beispiel für einen Eliminator Typen: es abstrahiert über das, was es liefert (das Motiv der Beseitigung) und es erfordert, dass Sie null oder mehr Methoden (eine, hier) des Erreichens des Motivs unter spezifischeren Umständen zu konstruieren. Der Weg es zu lesen ist rückwärts. Es sagt

Wenn Sie ein Problem haben (bewohnen ein anderes Motiv Typ t), und sonst niemand helfen kann, vielleicht können Sie Fortschritte machen, indem Zwang c in Ihrer Methode angenommen.

Da die Sprache der Zwänge Verbindung (aka fache Vervielfachung) zugibt, wir die Mittel erwerben Lemmata des Formulars

lemma :: forall x1 .. xn. (p1[x1 .. xn],.. pm[x1 .. xn])  -- premises 
         => t1[x1 .. xn] -> .. tl[x1 .. xn]  -- targets 
         -> Holds (c1[x1 .. xn],.. ck[x1 .. xn]) -- conclusions 

und es könnte sogar zu schreiben, dass einige Zwang, eine Prämisse p oder ein c Fassend hat die Form einer Gleichung

l[x1 .. xn] ~ r[x1 .. cn] 

nun, wie die Bereitstellung eines lemma, betrachten, das Problem der Füllung eines Lochs

_ :: Problem 

verfeinern dieses _ durch die Eliminierung lemma Angabe der Ziele . Das Motiv kommt von dem Problem zur Hand. Die Methode (Singular im Fall von Holds) bleibt offen.

lemma target1 .. targetl $ _ 

und das Verfahren Loch wird nicht Typ geändert

_ :: Problem 

aber GHC wird ein paar mehr Sachen kennen und somit eher Ihre Lösung zu glauben.

Manchmal gibt es eine Constraint-versus-Data-Auswahl, um festzulegen, was eine (Constraint-) Prämisse und was ein (Daten-) Ziel ist.Ich neige dazu, diese zu wählen, um Mehrdeutigkeiten zu vermeiden (Simon mag es zu schätzen x1 .. xn, aber manchmal braucht einen Hinweis) und Beweis durch Induktion, die viel einfacher auf Ziele ist (oft die Singletons für Typ-Level-Daten) als auf Prämissen.

In Bezug auf die Bereitstellung für Gleichungen, können Sie sicher auf einen Datentyp Präsentation wechseln und eine Fallanalyse

case dataLemma target1 .. targetl of Refl -> method 

ausbrechen und in der Tat, wenn Sie sich mit dem Dict existentielle

ausstatten

data Dict (c :: Constraint) :: * where 
    Dict :: c => Dict c 

Sie können ein Bündel auf einmal tun

case multiLemma blah blah blah of (Refl, Dict, Dict, Refl) -> method 

aber Die Eliminatorform ist kompakter und lesbarer , wenn es höchstens eine Methode gibt. Tatsächlich können wir mehrere Lemmata Kette, ohne jemals nach rechts Schiebe

lemma1 .. $ 
... 
lemmaj .. $ 
method 

Wenn Sie eine solche Eliminator mit zwei oder mehr Fälle haben, ich glaube, es ist oft besser, es zu einpacken als GADT, so dass die Einsatzorte helfend jeder Tag Fall mit einer Konstruktorbezeichnung.

Wie auch immer, ja, der Punkt ist, die Präsentation der Fakten zu wählen, die uns am kompaktesten ermöglicht, die Reichweite der Constraint-Solving-Maschinerie von GHC zu erweitern, so dass mehr Sachen nur checket. Wenn Sie mit Simon in Verlegenheit geraten, ist es oft eine gute Strategie, sich Dimitrios von nebenan zu erklären.