Gibt es in reinen Funktionssprachen wie Haskell einen Algorithmus, um die Umkehrung einer Funktion (Bearbeiten) zu erhalten, wenn sie bijektiv ist? Und gibt es eine bestimmte Möglichkeit, Ihre Funktion so zu programmieren, wie sie ist?
haskell
clojure
functional-programming
ocaml
MaiaVictor
quelle
quelle
f x = 1
die Umkehrung von 1 eine Menge von ganzen Zahlen ist und die Umkehrung von allem anderen eine leere Menge ist. Unabhängig davon, was einige Antworten sagen, ist die nicht bijektive Funktion nicht das größte Problem.f
eineg
solche Funktion , dassf . g = id
undg . f = id
. Ihr Kandidat prüft in diesem Fall nicht einmal.f x = 1
es keine Umkehrung gibt, einen sehr engen Ansatz verfolgen und die gesamte Komplexität des Problems ignorieren.Antworten:
In einigen Fällen ja! Es gibt ein wunderschönes Papier namens Bidirectionalization for Free! Hier werden einige Fälle erörtert, in denen es möglich ist, eine inverse Funktion vollständig automatisch abzuleiten, wenn Ihre Funktion ausreichend polymorph ist. (Außerdem wird erläutert, was das Problem schwierig macht, wenn die Funktionen nicht polymorph sind.)
Was Sie herausholen, wenn Ihre Funktion invertierbar ist, ist die Umkehrung (mit einer falschen Eingabe); In anderen Fällen erhalten Sie eine Funktion, die versucht, einen alten Eingabewert und einen neuen Ausgabewert zusammenzuführen.
quelle
put
Funktionen in alle Datensatzstrukturen, die abgeleitet wurdenData
: haskell.org/pipermail/haskell-cafe/2008-April/042193.html mit einem ähnlichen Ansatz wie das später (strenger, allgemeiner, prinzipieller usw.) in "kostenlos" präsentiert.Nein, das ist im Allgemeinen nicht möglich.
Beweis: Bijektive Funktionen des Typs berücksichtigen
mit
Angenommen, wir haben einen
inv :: F -> F
solchen Wechselrichterinv f . f ≡ id
. Angenommen, wir haben es auf die Funktion getestetf = id
, indem wir dies bestätigt habenDa dies zuerst
B0
in der Ausgabe nach einer begrenzten Zeit geschehen sein muss, haben wir eine Obergrenzen
sowohl für die Tiefe, bis zu derinv
unsere Testeingabe tatsächlich ausgewertet wurde, um dieses Ergebnis zu erhalten, als auch für die Häufigkeit, mit der sie aufgerufen werden kannf
. Definieren Sie jetzt eine Familie von FunktionenOffensichtlich für alle
0<j≤n
,g j
ist eine Bijektion, in der Tat selbst inverse. Wir sollten also in der Lage sein, dies zu bestätigenaber um dies zu erfüllen,
inv (g j)
hätte es auch nötig sein müsseng j (B1 : repeat B0)
bis zu einer Tiefe von bewertenn+j > n
head $ g j l
für mindestensn
unterschiedliche übereinstimmende Listen auswertenreplicate (n+j) B0 ++ B1 : ls
Bis zu diesem Zeitpunkt ist mindestens eine davon
g j
nicht zuf
unterscheiden und hätte, dainv f
sie keine dieser Bewertungen durchgeführt hatte,inv
sie möglicherweise nicht auseinanderhalten können - ohne einige Laufzeitmessungen allein durchzuführen, was nur in derIO Monad
.⬜
quelle
Sie können es auf Wikipedia nachschlagen, es heißt Reversible Computing .
Im Allgemeinen können Sie dies jedoch nicht tun, und keine der funktionalen Sprachen verfügt über diese Option. Beispielsweise:
Diese Funktion hat keine Umkehrung.
quelle
f
es eine Umkehrung gibt, es ist nur so, dass die Umkehrung eine nicht deterministische Funktion ist?g :: Int -> a
, die umgekehrt istf
, auch wenn Sie die Umkehrungf
mathematisch beschreiben können.f x = 2 * x
seif' x = [x / 2]
und dann das Gegenteil vonf _ = 1
istf' 1 = [minBound ..]; f' _ = []
. Das heißt, es gibt viele Umkehrungen für 1 und keine für einen anderen Wert.Nicht in den meisten funktionalen Sprachen, sondern in der Logikprogrammierung oder der relationalen Programmierung sind die meisten von Ihnen definierten Funktionen keine Funktionen, sondern "Beziehungen", und diese können in beide Richtungen verwendet werden. Siehe zum Beispiel Prolog oder Kanren.
quelle
Aufgaben wie diese sind fast immer unentscheidbar. Sie können eine Lösung für bestimmte Funktionen haben, jedoch nicht generell.
Hier können Sie nicht einmal erkennen, welche Funktionen eine Inverse haben. Zitat von Barendregt, HP Der Lambda-Kalkül: seine Syntax und Semantik. Nordholland, Amsterdam (1984) :
Nehmen wir A als die Menge der Lambda-Terme, die invertierbare Funktionen darstellen, und B den Rest. Beide sind nicht leer und werden unter Beta-Gleichheit geschlossen. Es ist also nicht möglich zu entscheiden, ob eine Funktion invertierbar ist oder nicht.
(Dies gilt für den untypisierten Lambda-Kalkül. TBH Ich weiß nicht, ob das Argument direkt an einen typisierten Lambda-Kalkül angepasst werden kann, wenn wir den Typ einer Funktion kennen, die wir invertieren möchten. Aber ich bin mir ziemlich sicher, dass dies der Fall sein wird ähnlich.)
quelle
Wenn Sie die Domäne der Funktion aufzählen und Elemente des Bereichs auf Gleichheit vergleichen können, können Sie dies auf recht einfache Weise. Mit Aufzählen meine ich, eine Liste aller verfügbaren Elemente zu haben. Ich bleibe bei Haskell, da ich Ocaml nicht kenne (oder sogar weiß, wie man es richtig kapitalisiert ;-)
Sie möchten die Elemente der Domäne durchlaufen und prüfen, ob sie dem Element des Bereichs entsprechen, den Sie invertieren möchten. Nehmen Sie dann das erste Element, das funktioniert:
Da Sie angegeben haben, dass
f
es sich um eine Bijektion handelt, muss es nur ein einziges solches Element geben. Der Trick besteht natürlich darin, sicherzustellen, dass Ihre Aufzählung der Domäne tatsächlich alle Elemente in einer endlichen Zeit erreicht . Wenn Sie eine Bijektion von zu invertieren sind versucht ,Integer
zuInteger
verwenden[0,1 ..] ++ [-1,-2 ..]
wird nicht funktionieren , wie Sie nie auf die negativen Zahlen zu bekommen. Konkretinv ([0,1 ..] ++ [-1,-2 ..]) (+1) (-3)
wird nie ein Wert ergeben.Funktioniert jedoch,
0 : concatMap (\x -> [x,-x]) [1..]
da dies die Ganzzahlen in der folgenden Reihenfolge durchläuft[0,1,-1,2,-2,3,-3, and so on]
. In der Tatinv (0 : concatMap (\x -> [x,-x]) [1..]) (+1) (-3)
sofort zurück-4
!Das Control.Monad.Omega- Paket kann Ihnen dabei helfen, Listen mit Tupeln usw. auf gute Weise durchzugehen . Ich bin mir sicher, dass es noch mehr solche Pakete gibt - aber ich kenne sie nicht.
Natürlich ist dieser Ansatz eher unaufdringlich und brutal, ganz zu schweigen von hässlich und ineffizient! Ich werde also mit ein paar Bemerkungen zum letzten Teil Ihrer Frage enden, wie man Bijektionen "schreibt". Das Typensystem von Haskell kann nicht beweisen, dass eine Funktion eine Bijektion ist - dafür wollen Sie wirklich so etwas wie Agda -, aber es ist bereit, Ihnen zu vertrauen.
(Warnung: Es folgt ungetesteter Code)
Können Sie also einen Datentyp von
Bijection
s zwischen den Typen definierena
undb
:zusammen mit so vielen Konstanten (wo Sie sagen können: "Ich weiß , dass es sich um Bijektionen handelt!"), wie Sie möchten, wie zum Beispiel:
und ein paar intelligente Kombinatoren wie:
Ich denke du könntest es dann tun
invert (mapBi add1Bi) [1,5,6]
und bekommen[0,4,5]
. Wenn Sie Ihre Kombinatoren auf intelligente Weise auswählen, kann die Häufigkeit, mit der Sie eineBi
Konstante von Hand schreiben müssen, sehr begrenzt sein.Wenn Sie wissen, dass eine Funktion eine Bijektion ist, haben Sie hoffentlich eine Beweisskizze dieser Tatsache in Ihrem Kopf, die der Curry-Howard-Isomorphismus in ein Programm verwandeln sollte :-)
quelle
Ich habe mich kürzlich mit solchen Problemen befasst, und nein, ich würde sagen, dass (a) es in vielen Fällen nicht schwierig ist, aber (b) es überhaupt nicht effizient ist.
Nehmen wir im Grunde an, Sie haben es
f :: a -> b
, und dasf
ist in der Tat eine bjiection. Sie können die Umkehrungf' :: b -> a
auf eine wirklich dumme Weise berechnen :Wenn
f
es sich um eine Bijektion handelt undenumerate
wirklich alle Werte von erzeugta
, werden Sie schließlich einea
solche treffen , dassf a == b
.Typen mit einer
Bounded
und einerEnum
Instanz können trivial erstellt werdenRecursivelyEnumerable
. Paare vonEnumerable
Typen können auch gemacht werdenEnumerable
:Gleiches gilt für Disjunktionen von
Enumerable
Typen:Die Tatsache, dass wir dies sowohl für
(,)
als auchEither
wahrscheinlich für jeden algebraischen Datentyp tun können.quelle
Nicht jede Funktion hat eine Umkehrung. Wenn Sie die Diskussion auf Eins-zu-Eins-Funktionen beschränken, können Sie durch die Möglichkeit, eine beliebige Funktion zu invertieren, jedes Kryptosystem knacken. Wir müssen irgendwie hoffen, dass dies auch theoretisch nicht machbar ist!
quelle
String encrypt(String key, String text)
ohne Schlüssel denken, können Sie immer noch nichts tun. EDIT: Plus was Delnan gesagt hat.In einigen Fällen ist es möglich, die Umkehrung einer bijektiven Funktion zu finden, indem sie in eine symbolische Darstellung umgewandelt wird. Anhand dieses Beispiels habe ich dieses Haskell-Programm geschrieben, um Umkehrungen einiger einfacher Polynomfunktionen zu finden:
Dieses Beispiel funktioniert nur mit arithmetischen Ausdrücken, aber es könnte wahrscheinlich verallgemeinert werden, um auch mit Listen zu arbeiten.
quelle
Nein, nicht alle Funktionen haben sogar Inversen. Was wäre zum Beispiel die Umkehrung dieser Funktion?
quelle