Gibt es in reinen Funktionssprachen einen Algorithmus, um die Umkehrfunktion zu erhalten?

100

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?

MaiaVictor
quelle
5
Mathematisch ist es nicht falsch zu sagen, dass im Fall von f x = 1die 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.
Karolis Juodelė
2
Die richtige Antwort lautet JA, ist aber nicht effizient. Sei f: A -> B und A endlich, dann müssen Sie bei b € B "nur" alle f (A) untersuchen, um alle a € A zu finden, die f (a) = b sind. In einem Quantencomputer hätte O (Größe (a)) möglicherweise Komplexität. Natürlich suchen Sie nach einem praktischen Algorithmus. Es ist nicht (hat O (2 ^ Größe (a))), sondern existiert ...
Josejuan
QuickCheck macht es genau (sie suchen in f: A -> Bool nach einem False).
Josejuan
4
@ KarolisJuodelė: Ich bin anderer Meinung; das ist normalerweise nicht das, was mit invers gemeint ist. Fast jedes Mal, wenn ich auf den Begriff stoße, ist die Umkehrung von feine gsolche Funktion , dass f . g = idund g . f = id. Ihr Kandidat prüft in diesem Fall nicht einmal.
Ben Millwood
3
@ BenMillwood, du hast recht. Was ich gesagt habe, heißt inverses Bild, keine inverse Funktion. Mein Punkt war, dass die Antworten, die darauf hinweisen, dass f x = 1es keine Umkehrung gibt, einen sehr engen Ansatz verfolgen und die gesamte Komplexität des Problems ignorieren.
Karolis Juodelė

Antworten:

101

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.

Daniel Wagner
quelle
3
Hier ist ein neueres Papier, das den Stand der Bidirektionalisierung untersucht. Es enthält drei Familien von Techniken, einschließlich "syntaktischer" und kombinatorbasierter Ansätze: iai.uni-bonn.de/~jv/ssgip-bidirectional-final.pdf
sclv
Und um nur zu erwähnen, im Jahr 2008 gab es diese Nachricht an -cafe, mit einem bösen Hack zum Invertieren von putFunktionen in alle Datensatzstrukturen, die abgeleitet wurden Data: 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.
sclv
Es ist 2017 und natürlich ist der Link zum Artikel
Mina Gabriel
37

Nein, das ist im Allgemeinen nicht möglich.

Beweis: Bijektive Funktionen des Typs berücksichtigen

type F = [Bit] -> [Bit]

mit

data Bit = B0 | B1

Angenommen, wir haben einen inv :: F -> Fsolchen Wechselrichter inv f . f ≡ id. Angenommen, wir haben es auf die Funktion getestet f = id, indem wir dies bestätigt haben

inv f (repeat B0) -> (B0 : ls)

Da dies zuerst B0in der Ausgabe nach einer begrenzten Zeit geschehen sein muss, haben wir eine Obergrenze nsowohl für die Tiefe, bis zu der invunsere Testeingabe tatsächlich ausgewertet wurde, um dieses Ergebnis zu erhalten, als auch für die Häufigkeit, mit der sie aufgerufen werden kann f. Definieren Sie jetzt eine Familie von Funktionen

g j (B1 : B0 : ... (n+j times) ... B0 : ls)
   = B0 : ... (n+j times) ... B0 : B1 : ls
g j (B0 : ... (n+j times) ... B0 : B1 : ls)
   = B1 : B0 : ... (n+j times) ... B0 : ls
g j l = l

Offensichtlich für alle 0<j≤n, g jist eine Bijektion, in der Tat selbst inverse. Wir sollten also in der Lage sein, dies zu bestätigen

inv (g j) (replicate (n+j) B0 ++ B1 : repeat B0) -> (B1 : ls)

aber um dies zu erfüllen, inv (g j)hätte es auch nötig sein müssen

  • g j (B1 : repeat B0)bis zu einer Tiefe von bewertenn+j > n
  • head $ g j lfür mindestens nunterschiedliche übereinstimmende Listen auswertenreplicate (n+j) B0 ++ B1 : ls

Bis zu diesem Zeitpunkt ist mindestens eine davon g jnicht zu funterscheiden und hätte, da inv fsie keine dieser Bewertungen durchgeführt hatte, invsie möglicherweise nicht auseinanderhalten können - ohne einige Laufzeitmessungen allein durchzuführen, was nur in der IO Monad.

                                                                                                                                   ⬜

links herum
quelle
19

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:

f :: a -> Int
f _ = 1

Diese Funktion hat keine Umkehrung.

mck
quelle
1
Wäre es falsch zu sagen, dass fes eine Umkehrung gibt, es ist nur so, dass die Umkehrung eine nicht deterministische Funktion ist?
Matt Fenwick
10
@MattFenwick In einer Sprache wie Haskell sind Funktionen einfach nicht nicht deterministisch (ohne die Typen und die Art und Weise, wie Sie sie verwenden, zu ändern). Es gibt keine Haskell-Funktion g :: Int -> a, die umgekehrt ist f, auch wenn Sie die Umkehrung fmathematisch beschreiben können.
Ben
2
@Matt: Schauen Sie in der funktionalen Programmierung und Logik nach "unten". Ein "Boden" ist ein "unmöglicher" Wert, entweder weil er widersprüchlich, nicht terminierend oder die Lösung eines unentscheidbaren Problems ist (dies ist mehr als nur widersprüchlich - wir können eine Lösung methodisch "verfolgen", während wir ein Design untersuchen Leerzeichen mit "undefined" und "error" während der Entwicklung). Ein "unteres" x hat den Typ a. Es "bewohnt" (oder ist ein "Wert") jeder Art. Dies ist ein logischer Widerspruch, da Typen Sätze sind und es keinen Wert gibt, der jeden Satz erfüllt. Schauen Sie auf Haskell-Cafe für gute Diskussionen
Nomen
2
@Matt: Anstatt die Nichtexistenz von Inversen als Nichtdeterminismus zu charakterisieren, muss man sie als Bottoms charakterisieren. Die Umkehrung von f _ = 1 ist unten, da sie jeden Typ bewohnen muss (alternativ ist sie unten, da f für keinen Typ mit mehr als einem einzelnen Element eine Umkehrfunktion hat - der Aspekt, auf den Sie sich konzentriert haben, denke ich). Bottom zu sein kann sowohl positiv als auch negativ als Aussage über Werte verstanden werden. Man kann vernünftigerweise von der Umkehrung einer beliebigen Funktion als dem "Wert" unten sprechen. (Auch wenn es nicht "wirklich" ein Wert ist)
Nomen
1
Nachdem ich viel später hierher zurückgekommen bin, sehe ich, worum es bei Matt geht: Wir modellieren den Nichtdeterminismus oft über Listen, und wir könnten dasselbe für Umkehrungen tun. Das Gegenteil von f x = 2 * xsei f' x = [x / 2]und dann das Gegenteil von f _ = 1ist f' 1 = [minBound ..]; f' _ = []. Das heißt, es gibt viele Umkehrungen für 1 und keine für einen anderen Wert.
Amalloy
16

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.

Amalloy
quelle
1
Oder Merkur , der sonst viel vom Geist von Haskell teilt. - Guter Punkt, +1.
links um den
11

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) :

Eine Menge von Lambda-Begriffen ist nicht trivial, wenn es sich weder um eine leere noch um eine vollständige Menge handelt. Wenn A und B zwei nichttriviale, disjunkte Mengen von Lambda-Termen sind, die unter (Beta) -Gleichheit geschlossen sind, sind A und B rekursiv untrennbar.

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.)

Petr Pudlák
quelle
11

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:

inv :: Eq b => [a] -> (a -> b) -> (b -> a)
inv domain f b = head [ a | a <- domain, f a == b ]

Da Sie angegeben haben, dass fes 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 , Integerzu Integerverwenden [0,1 ..] ++ [-1,-2 ..]wird nicht funktionieren , wie Sie nie auf die negativen Zahlen zu bekommen. Konkret inv ([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 Tat inv (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 Bijections zwischen den Typen definieren aund b:

data Bi a b = Bi {
    apply :: a -> b,
    invert :: b -> a 
}

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:

notBi :: Bi Bool Bool
notBi = Bi not not

add1Bi :: Bi Integer Integer
add1Bi = Bi (+1) (subtract 1)

und ein paar intelligente Kombinatoren wie:

idBi :: Bi a a 
idBi = Bi id id

invertBi :: Bi a b -> Bi b a
invertBi (Bi a i) = (Bi i a)

composeBi :: Bi a b -> Bi b c -> Bi a c
composeBi (Bi a1 i1) (Bi a2 i2) = Bi (a2 . a1) (i1 . i2)

mapBi :: Bi a b -> Bi [a] [b]
mapBi (Bi a i) = Bi (map a) (map i)

bruteForceBi :: Eq b => [a] -> (a -> b) -> Bi a b
bruteForceBi domain f = Bi f (inv domain f)

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 eine BiKonstante 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 :-)

yatima2975
quelle
6

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 das fist in der Tat eine bjiection. Sie können die Umkehrung f' :: b -> aauf eine wirklich dumme Weise berechnen :

import Data.List

-- | Class for types whose values are recursively enumerable.
class Enumerable a where
    -- | Produce the list of all values of type @a@.
    enumerate :: [a]

 -- | Note, this is only guaranteed to terminate if @f@ is a bijection!
invert :: (Enumerable a, Eq b) => (a -> b) -> b -> Maybe a
invert f b = find (\a -> f a == b) enumerate

Wenn fes sich um eine Bijektion handelt und enumeratewirklich alle Werte von erzeugt a, werden Sie schließlich eine asolche treffen , dassf a == b .

Typen mit einer Boundedund einer EnumInstanz können trivial erstellt werden RecursivelyEnumerable. Paare von EnumerableTypen können auch gemacht werden Enumerable:

instance (Enumerable a, Enumerable b) => Enumerable (a, b) where
    enumerate = crossWith (,) enumerate enumerate

crossWith :: (a -> b -> c) -> [a] -> [b] -> [c]
crossWith f _ [] = []
crossWith f [] _ = []
crossWith f (x0:xs) (y0:ys) =
    f x0 y0 : interleave (map (f x0) ys) 
                         (interleave (map (flip f y0) xs)
                                     (crossWith f xs ys))

interleave :: [a] -> [a] -> [a]
interleave xs [] = xs
interleave [] ys = []
interleave (x:xs) ys = x : interleave ys xs

Gleiches gilt für Disjunktionen von EnumerableTypen:

instance (Enumerable a, Enumerable b) => Enumerable (Either a b) where
    enumerate = enumerateEither enumerate enumerate

enumerateEither :: [a] -> [b] -> [Either a b]
enumerateEither [] ys = map Right ys
enumerateEither xs [] = map Left xs
enumerateEither (x:xs) (y:ys) = Left x : Right y : enumerateEither xs ys

Die Tatsache, dass wir dies sowohl für (,)als auch Eitherwahrscheinlich für jeden algebraischen Datentyp tun können.

Luis Casillas
quelle
5

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!

Jeffrey Scofield
quelle
13
Jedes Kryptosystem (mit Ausnahme einiger ungerader, wie einmaliger Pads, die aus anderen Gründen nicht durchführbar sind) kann durch rohe Gewalt geknackt werden. Das macht sie nicht weniger nützlich und wäre auch keine unpraktisch teure Inversionsfunktion.
Tut es wirklich? Wenn Sie an eine Verschlüsselungsfunktion String encrypt(String key, String text)ohne Schlüssel denken, können Sie immer noch nichts tun. EDIT: Plus was Delnan gesagt hat.
mck
@MaciekAlbin Hängt von Ihrem Angriffsmodell ab. Ausgewählte Klartextangriffe können beispielsweise das Extrahieren des Schlüssels ermöglichen, wodurch andere mit diesem Schlüssel verschlüsselte Chiffretexte angegriffen werden können.
Mit "machbar" meinte ich etwas, das in angemessener Zeit erledigt werden kann. Ich meinte nicht "berechenbar" (ich bin mir ziemlich sicher).
Jeffrey Scofield
@ JeffreyScofield Ich verstehe Ihren Standpunkt. Aber ich muss sagen, ich bin verwirrt von "theoretisch machbar" - bezieht sich (unsere Definition von) Machbarkeit nicht nur darauf, wie schwierig es ist, praktisch zu tun?
5

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:

bijective_function x = x*2+1

main = do
    print $ bijective_function 3
    print $ inverse_function bijective_function (bijective_function 3)

data Expr = X | Const Double |
            Plus Expr Expr | Subtract Expr Expr | Mult Expr Expr | Div Expr Expr |
            Negate Expr | Inverse Expr |
            Exp Expr | Log Expr | Sin Expr | Atanh Expr | Sinh Expr | Acosh Expr | Cosh Expr | Tan Expr | Cos Expr |Asinh Expr|Atan Expr|Acos Expr|Asin Expr|Abs Expr|Signum Expr|Integer
       deriving (Show, Eq)

instance Num Expr where
    (+) = Plus
    (-) = Subtract
    (*) = Mult
    abs = Abs
    signum = Signum
    negate = Negate
    fromInteger a = Const $ fromIntegral a

instance Fractional Expr where
    recip = Inverse
    fromRational a = Const $ realToFrac a
    (/) = Div

instance Floating Expr where
    pi = Const pi
    exp = Exp
    log = Log
    sin = Sin
    atanh = Atanh
    sinh = Sinh
    cosh = Cosh
    acosh = Acosh
    cos = Cos
    tan = Tan
    asin = Asin
    acos = Acos
    atan = Atan
    asinh = Asinh

fromFunction f = f X

toFunction :: Expr -> (Double -> Double)
toFunction X = \x -> x
toFunction (Negate a) = \a -> (negate a)
toFunction (Const a) = const a
toFunction (Plus a b) = \x -> (toFunction a x) + (toFunction b x)
toFunction (Subtract a b) = \x -> (toFunction a x) - (toFunction b x)
toFunction (Mult a b) = \x -> (toFunction a x) * (toFunction b x)
toFunction (Div a b) = \x -> (toFunction a x) / (toFunction b x)


with_function func x = toFunction $ func $ fromFunction x

simplify X = X
simplify (Div (Const a) (Const b)) = Const (a/b)
simplify (Mult (Const a) (Const b)) | a == 0 || b == 0 = 0 | otherwise = Const (a*b)
simplify (Negate (Negate a)) = simplify a
simplify (Subtract a b) = simplify ( Plus (simplify a) (Negate (simplify b)) )
simplify (Div a b) | a == b = Const 1.0 | otherwise = simplify (Div (simplify a) (simplify b))
simplify (Mult a b) = simplify (Mult (simplify a) (simplify b))
simplify (Const a) = Const a
simplify (Plus (Const a) (Const b)) = Const (a+b)
simplify (Plus a (Const b)) = simplify (Plus (Const b) (simplify a))
simplify (Plus (Mult (Const a) X) (Mult (Const b) X)) = (simplify (Mult (Const (a+b)) X))
simplify (Plus (Const a) b) = simplify (Plus (simplify b) (Const a))
simplify (Plus X a) = simplify (Plus (Mult 1 X) (simplify a))
simplify (Plus a X) = simplify (Plus (Mult 1 X) (simplify a))
simplify (Plus a b) = (simplify (Plus (simplify a) (simplify b)))
simplify a = a

inverse X = X
inverse (Const a) = simplify (Const a)
inverse (Mult (Const a) (Const b)) = Const (a * b)
inverse (Mult (Const a) X) = (Div X (Const a))
inverse (Plus X (Const a)) = (Subtract X (Const a))
inverse (Negate x) = Negate (inverse x)
inverse a = inverse (simplify a)

inverse_function x = with_function inverse x

Dieses Beispiel funktioniert nur mit arithmetischen Ausdrücken, aber es könnte wahrscheinlich verallgemeinert werden, um auch mit Listen zu arbeiten.

Anderson Green
quelle
4

Nein, nicht alle Funktionen haben sogar Inversen. Was wäre zum Beispiel die Umkehrung dieser Funktion?

f x = 1
Dirk Holsopple
quelle
Ihre Funktion ist eine Konstante, hier geht es um bijektive Funktionen.
Soleil - Mathieu Prévot