Frage Hat ein `(a -> b) -> b 'äquivalent zu einem' a '?


In einer reinen funktionalen Sprache ist das einzige, was Sie mit einem Wert tun können, eine Funktion darauf anzuwenden.

Mit anderen Worten, wenn Sie etwas Interessantes mit einem Wert vom Typ machen wollen a Sie benötigen eine Funktion (zum Beispiel) mit type f :: a -> b und dann wenden Sie es an. Wenn jemand dich übergibt (flip apply) a mit Typ (a -> b) -> b, ist das ein geeigneter Ersatz für a?

Und was würdest du etwas mit Typ nennen? (a -> b) -> b? Es scheint, als wäre es ein Stellvertreter für eine aIch wäre versucht, es als Proxy zu bezeichnen http://www.thesaurus.com/browse/proxy.


37
2017-07-24 18:50


Ursprung


Antworten:


Luquis Antwort ist ausgezeichnet, aber ich werde eine andere Erklärung anbieten forall b. (a -> b) -> b === a aus ein paar Gründen: Erstens, weil ich der Meinung bin, dass die Verallgemeinerung zu Codesity etwas zu enthusiastisch ist. Und zweitens, weil es eine Gelegenheit ist, eine Menge interessanter Dinge zusammen zu binden. Weiter!

z5hs Zauberkiste

Stellen Sie sich vor, jemand hat eine Münze umgedreht und dann in eine magische Schachtel gelegt. Sie können nicht in der Box sehen, aber wenn Sie einen Typ wählen b und übergeben Sie der Box eine Funktion mit dem Typ Bool -> b, die Box spuckt aus b. Was können wir über diese Box lernen, ohne hineinzusehen? Können wir erfahren, wie der Zustand der Münze ist? Können wir lernen, welchen Mechanismus die Box benutzt, um die b? Wie sich herausstellt, können wir beides machen.

Wir können die Box als a definieren Rang 2 Funktion des Typs Box Bool woher

type Box a = forall b. (a -> b) -> b

(Hier bedeutet der Rang-2-Typ, dass der Box-Hersteller wählt a und der Boxbenutzer wählt b.)

Wir legen die a in der Box und dann schließen wir die Box, erstellen ... a Schließung.

-- Put the a in the box.
box :: a -> Box a
box a f = f a

Beispielsweise, box True. Partielle Anwendung ist nur eine clevere Möglichkeit, Schließungen zu erstellen!

Nun, ist die Münze Kopf oder Zahl? Da darf ich, der Box-User, wählen b, Ich kann wählen Bool und eine Funktion übergeben Bool -> Bool. Wenn ich wähle id :: Bool -> Bool dann die Frage ist: Wird die Box den Wert ausspucken? Die Antwort ist, dass die Box entweder den Wert ausspuckt oder Unsinn ausspuckt (ein Grundwert wie undefined). Mit anderen Worten, wenn Sie eine Antwort bekommen, dann diese Antwort Muss sei richtig.

-- Get the a out of the box.
unbox :: Box a -> a
unbox f = f id

Da wir in Haskell keine willkürlichen Werte erzeugen können, ist die einzige sinnvolle Sache, die die Box machen kann, die gegebene Funktion auf den Wert anzuwenden, den sie versteckt. Dies ist eine Folge des parametrischen Polymorphismus, auch bekannt als parametrisch.

Um das zu zeigen Box a ist isomorph zu aWir müssen zwei Dinge über Boxen und Unboxing beweisen. Wir müssen beweisen, dass Sie herausbekommen, was Sie hineingelegt haben und dass Sie hineinlegen können, was Sie herausbekommen.

unbox . box = id
box . unbox = id

Ich mache den ersten und lasse den zweiten als Übung für den Leser.

  unbox . box
= {- definition of (.) -}
  \b -> unbox (box b)
= {- definition of unbox and (f a) b = f a b -}
  \b -> box b id
= {- definition of box -}
  \b -> id b
= {- definition of id -}
  \b -> b
= {- definition of id, backwards -}
  id

(Wenn diese Beweise eher trivial erscheinen, liegt das daran, dass alle (vollständigen) polymorphen Funktionen in Haskell natürliche Transformationen sind und was wir hier beweisen ist Natürlichkeit. Die Parametrizität liefert uns wieder Sätze für niedrige, niedrige Preise!)

Als eine Nebenübung und eine andere Übung für den Leser, warum kann ich nicht wirklich definieren rebox mit (.)?

rebox = box . unbox

Warum muss ich die Definition von (.) ich selbst wie eine Art Höhlenmensch?

rebox :: Box a -> Box a
rebox f = box (unbox f)

(Tipp: Was sind die Arten von box, unbox, und (.)?)

Identität und Codensität und Yoneda, Oh mein!

Nun, wie können wir verallgemeinern? Box? Luqui verwendet Codesättigung: beide bs werden durch einen Konstruktor beliebigen Typs verallgemeinert, den wir aufrufen werden f. Dies ist die Codensität verwandeln von f a.

type CodenseBox f a = forall b. (a -> f b) -> f b

Wenn wir reparieren f ~ Identity dann kommen wir zurück Box. Es gibt jedoch noch eine andere Möglichkeit: Wir können nur den Rückgabetyp mit treffen f:

type YonedaBox f a = forall b. (a -> b) -> f b

(Ich habe das Spiel hier mit diesem Namen verschenkt, aber wir werden darauf zurückkommen.) Wir können auch reparieren f ~ Identity hier um sich zu erholen Box, aber wir lassen den Boxbenutzer eher in einer normalen Funktion als in einem Kleisli-Pfeil. Verstehen Was wir verallgemeinern, schauen wir uns noch einmal die Definition von box:

box a f = f a

Nun, das ist gerecht flip ($), nicht wahr? Und es stellt sich heraus, dass unsere anderen zwei Boxen durch Verallgemeinern entstehen ($): CodenseBox ist eine partiell aufgetragene, gespaltene monadische Bindung und YonedaBox ist ein teilweise angewendet flip fmap. (Dies erklärt auch, warum Codensity f ist ein Monad und Yoneda f ist ein Functor zum irgendein Wahl von f: Die einzige Möglichkeit, eine zu erstellen, besteht darin, eine bind- bzw. fmap-Datei zu schließen. Außerdem sind beide Begriffe der esoterischen Kategorientheorie wirklich Verallgemeinerungen eines Konzepts, das vielen arbeitenden Programmierern vertraut ist: die CPS-Transformation!

Mit anderen Worten, YonedaBox ist die Yoneda Embedding und die richtig abstrahiert box/unbox Gesetze für YonedaBox sind der Beweis für das Yoneda Lemma!

TL; DR:

forall b. (a -> b) -> b === a ist eine Instanz des Yoneda Lemma.


44
2017-07-24 23:55



Diese Frage ist ein Fenster zu einer Reihe von tieferen Konzepten.

Beachten Sie zunächst, dass diese Frage zweideutig ist. Meinen wir den Typ? forall b. (a -> b) -> b, so dass wir instanziieren können b mit welchem ​​Typ auch immer, oder meinen wir es? (a -> b) -> b für einige spezifische b das können wir nicht wählen.

Wir können diese Unterscheidung in Haskell formalisieren:

newtype Cont b a = Cont ((a -> b) -> b)
newtype Cod a    = Cod (forall b. (a -> b) -> b)

Hier sehen wir ein Vokabular. Der erste Typ ist der Cont Monade, die zweite ist CodensityIdentityobwohl meine Vertrautheit mit letzterem Begriff nicht stark genug ist, um zu sagen, was man das auf Englisch nennen sollte.

Cont b a kann nicht gleichwertig sein a es sei denn a -> b kann mindestens so viele Informationen enthalten wie a (siehe Dan Robertsons Kommentar unten). Beachten Sie zum Beispiel, dass Sie nie etwas herausholen können ContVoida.

Cod a ist äquivalent zu a. Um dies zu sehen, genügt es, den Isomorphismus zu beobachten:

toCod :: a -> Cod a
fromCod :: Cod a -> a

deren Implementierungen ich als Übung verlassen werde. Wenn du es wirklich machen willst, kannst du versuchen zu beweisen, dass dieses Paar wirklich ein Isomorphismus ist. fromCod . toCod = id ist einfach, aber toCod . fromCod = id benötigt die freier Satz zum Cod.


27
2017-07-24 19:50



Die anderen Antworten haben eine großartige Arbeit geleistet und die Beziehung zwischen den Typen beschrieben forall b . (a -> b) -> b und aIch möchte jedoch auf einen Vorbehalt hinweisen, da er zu einigen interessanten offenen Fragen führt, an denen ich gearbeitet habe.

Technisch, forall b . (a -> b) -> b und a sind nicht isomorph in einer Sprache wie Haskell, die (1) Ihnen erlaubt, einen Ausdruck zu schreiben, der nicht terminiert und (2) entweder call-by-value (strict) oder enthält seq. Mein Punkt hier ist nicht etwas pingelig zu sein oder zu zeigen, dass die Parameterik in Haskell geschwächt ist (wie bekannt), aber dass es vielleicht ordentliche Wege gibt, sie zu stärken und in gewissem Sinne Isomorphismen wie diese zurückzugewinnen.

Es gibt einige Arten von Typ forall b . (a -> b) -> b das kann nicht ausgedrückt werden als a. Um zu sehen, warum, schauen wir uns zuerst den Beweis an, den Rein als Übung hinterlassen hat. box . unbox = id. Es stellt sich heraus, dass dieser Beweis tatsächlich interessanter ist als der in seiner Antwort, da er sich auf Parameterik in entscheidender Weise stützt.

box . unbox
= {- definition of (.) -}
  \m -> box (unbox m)
= {- definition of box -}
  \m f -> f (unbox m)
= {- definition of unbox -}
  \m f -> f (m id)
= {- free theorem: f (m id) = m f -}
  \m f -> m f
= {- eta: (\f -> m f) = m -}
  \m -> m
= {- definition of id, backwards -}
  id

Der interessante Schritt, bei dem die Parametrisierung ins Spiel kommt, ist die Anwendung des freier Satz  f (m id) = m f. Diese Eigenschaft ist eine Konsequenz von forall b . (a -> b) -> b, die Art von m. Wenn wir daran denken m als eine Box mit einem zugrunde liegenden Wert des Typs a drinnen, dann das Einzige m kann mit seinem Argument tun es auf diesen zugrunde liegenden Wert anwenden und das Ergebnis zurückgeben. Auf der linken Seite bedeutet das, dass f (m id) extrahiert den zugrunde liegenden Wert aus der Box und übergibt ihn an f. Auf der rechten Seite bedeutet das, dass m gilt f direkt auf den zugrunde liegenden Wert.

Leider ist diese Argumentation nicht ganz haltbar, wenn wir Begriffe wie die m und f unten.

m :: (Bool -> b) -> b
m k = seq (k true) (k false)

f :: Bool -> Int
f x = if x then ⊥ else 2`

Erinnern wir uns, wir wollten zeigen f (m id) = m f

f (m id)
= {- definition f -}
  if (m id) then ⊥ else 2
= {- definition of m -}
  if (seq (id true) (id false)) then ⊥ else 2
= {- definition of id -}
  if (seq true (id false)) then ⊥ else 2
= {- definition of seq -}
  if (id false) then ⊥ else 2
= {- definition of id -}
  if false then ⊥ else 2
= {- definition of if -}
  2

m f
= {- definition of m -}
  seq (f true) (f false)
= {- definition of f -}
  seq (if true then ⊥ else 2) (f false)
= {- definition of if -}
  seq ⊥ (f false)
= {- definition of seq -}
  ⊥

Deutlich 2 ist ungleich zu  so haben wir unseren freien Satz und den Isomorphismus zwischen verloren a und (a -> b) -> b damit. Aber was ist genau passiert? Im Wesentlichen, m ist nicht nur eine gut behaarte Box, weil sie ihr Argument auf zwei verschiedene zugrunde liegende Werte anwendet (und verwendet) seq um sicherzustellen, dass diese beiden Anwendungen tatsächlich evaluiert werden), was wir beobachten können, indem wir eine Fortsetzung durchlaufen, die auf einem dieser Grundwerte endet, aber nicht auf dem anderen. Mit anderen Worten, m id = false ist nicht wirklich eine getreue Darstellung von m Als ein Bool weil es die Tatsache "vergisst", dass m ruft seine Eingabe mit auf beide  true und false.

Das Problem ist ein Ergebnis der Interaktion zwischen drei Dingen:

  1. Die Anwesenheit von Nicht-Beendigung.
  2. Das Vorhandensein von Seq.
  3. Die Tatsache, dass die Bedingungen des Typs forall b . (a -> b) -> b kann ihre Eingabe mehrmals anwenden.

Es gibt wenig Hoffnung, um Punkt 1 oder 2 herumzukommen. Lineare Typen kann uns aber eine Chance geben, das dritte Thema zu bekämpfen. EIN lineare Funktion vom Typ a ⊸ b ist eine Funktion vom Typ a tippen b welches seine Eingabe genau einmal verwenden muss. Wenn wir es benötigen m um den Typ zu haben forall b . (a -> b) ⊸ b, dann schließt dies unser Gegenbeispiel zum freien Satz aus und soll uns einen Isomorphismus zwischen uns zeigen lassen a und forall b . (a -> b) ⊸ b  sogar in der Anwesenheit von Nichtterminierung und seq.

Das ist wirklich cool! Es zeigt, dass die Linearität die Fähigkeit besitzt, interessante Eigenschaften zu retten, indem sie Effekte zähmt, die eine echte Gleichsetzung erschweren können.

Ein großes Problem bleibt jedoch. Wir haben noch keine Techniken, um den freien Satz zu beweisen, den wir für den Typ brauchen forall b . (a -> b) ⊸ b. Es stellt sich heraus, dass die aktuellen logischen Beziehungen (die Werkzeuge, die wir normalerweise für solche Beweise verwenden) nicht dafür ausgelegt sind, die Linearität in der benötigten Weise zu berücksichtigen. Dieses Problem hat Auswirkungen auf die Korrektheit von Compilern, die CPS-Übersetzungen durchführen.


12
2017-07-25 18:24