In reinen funktionalen Sprachen gibt es einen Algorithmus, um die inverse Funktion?

Nein, es ist nicht möglich im Allgemeinen.

Beweis: betrachten bijektive Funktionen vom Typ

type F = [Bit] -> [Bit]

mit

data Bit = B0 | B1

Angenommen, wir haben einen Wechselrichter inv :: F -> F so dass inv f . f ≡ id. Sagen wir, wir haben es getestet für die Funktion f = id, mit der Bestätigung, dass

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

Seit diesem ersten B0 in die Ausgabe gekommen sein muss, nachdem eine begrenzte Zeit, wir haben eine Obere Grenze n sowohl die Tiefe, bis zu der inv hatte tatsächlich ausgewertet unser test-Eingang um dieses Resultat zu bekommen, sowie die Anzahl der Zeiten, die Sie haben können, genannt f. Definieren Sie nun 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

Klar, für alle 0<j≤n, g j ist eine bijection, in der Tat selbst-invers. Wir sollten also in der Lage sein, um zu bestätigen,

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

aber dieses erfüllen, inv (g j) müsste entweder

• bewerten g j (B1 : repeat B0) bis zu einer Tiefe von n+j > n
• bewerten head $ g j l für mindestens n verschiedenen Listen passenden replicate (n+j) B0 ++ B1 : ls

Bis zu diesem Punkt, mindestens eine der g j ist nicht von f, und da inv f noch nicht getan haben, entweder von diesen Auswertungen inv konnte unmöglich gesagt haben, es auseinander – kurz, zu tun, einige Laufzeit-Messungen auf seine eigene, und das ist nur möglich in der IO Monad.

                                                                                                                                   ⬜

Nicht in den meisten funktionalen Sprachen, aber in der Logik der Programmierung bzw. der relationalen Programmierung, die meisten Funktionen, die Sie definieren, sind in Wirklichkeit nicht um Funktionen, sondern "Beziehungen", und diese kann in beiden Richtungen verwendet werden. Siehe zum Beispiel prolog oder kanren.

Wenn Sie aufzählen können, die in der Domäne der Funktion und vergleichen können, - Elemente der Reihe für die Gleichstellung, Sie kann - in einer eher einfachen Art und Weise. Durch aufzählen ich, dass man eine Liste aller verfügbaren Elemente. Ich bleibe bei Haskell, da ich nicht weiß, Ocaml (oder sogar, wie zu profitieren ist es richtig 😉

Was Sie tun möchten, ist laufen durch die Elemente der Domäne und sehen, ob Sie gleich dem element des Bereichs, den Sie versuchen zu invertieren, und nehmen Sie die erste, der funktioniert:

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

Da Sie erklärt habe, dass f ist eine bijection, gibt es zwangsläufig ein und nur ein solches element. Der trick, natürlich, ist, um sicherzustellen, dass Ihre Aufzählung der domain tatsächlich erreicht alle Elemente in einer endlichen Zeit. Wenn Sie versuchen, zu invertieren bijection von Integer zu Integer mit [0,1 ..] ++ [-1,-2 ..] wird nicht funktionieren, da wirst du aber nie bekommen, um die negativen zahlen. Konkret inv ([0,1 ..] ++ [-1,-2 ..]) (+1) (-3) niemals ergeben Sie einen Wert.

Jedoch 0 : concatMap (\x -> [x,-x]) [1..] arbeiten, wie das läuft durch die ganzen zahlen in der folgenden Reihenfolge [0,1,-1,2,-2,3,-3, and so on]. In der Tat inv (0 : concatMap (\x -> [x,-x]) [1..]) (+1) (-3) umgehend zurück -4!

Den Kontrolle.Monade.Omega Paket kann Ihnen helfen, führen Sie durch Listen von Tupeln usw. in einem guten Weg; ich bin sicher, es gibt mehr Pakete wie, aber ich kenne Sie nicht.

Natürlich, dieser Ansatz ist eher low-Stirn-und brute-force, nicht zu erwähnen, hässlich und ineffizient! Also werde ich Ende mit ein paar Bemerkungen zu dem letzten Teil deiner Frage, wie 'schreiben' bijections. Das Typsystem von Haskell ist nicht up, um zu beweisen, dass eine Funktion eine bijection - wollen Sie wirklich so etwas wie Agda - aber es ist bereit, Ihnen zu Vertrauen.

(Achtung: ungetestet-code folgt)

So können Sie definieren einen Datentyp Bijection s zwischen Arten a und b:

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

zusammen mit so vielen Konstanten (wo man sagen kann 'ich wissen Sie sind bijections!') wie Sie möchten, wie:

notBi :: Bi Bool Bool
notBi = Bi not not

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

und ein paar smart-combinators, 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, Sie könnten dann tun invert (mapBi add1Bi) [1,5,6] und bekommen [0,4,5]. Wenn Sie wählen Sie Ihre combinators in eine intelligente Art und Weise, ich denke, die Anzahl der Zeiten, die Sie haben zu schreiben, eine Bi ständige von hand könnte ziemlich begrenzt.

Nach allem, wenn Sie wissen eine Funktion ist eine bijection, du wirst hoffentlich ein Beweis-Skizze, die Tatsache in den Kopf, die die Curry-Howard Isomorphie sollte in der Lage sein wiederum in ein Programm 🙂

Nicht jede Funktion hat eine inverse. Wenn Sie beschränken die Diskussion um one-to-one-Funktionen, die Fähigkeit zum umkehren einer beliebigen Funktion ermöglicht das knacken jedes Kryptosystem. Wir müssen hoffen, dass dies nicht möglich ist, auch in der Theorie!

In einigen Fällen ist es möglich, die inverse zu finden, der eine bijektive Funktion durch Umwandlung in eine symbolische Darstellung. Basierend auf dieses Beispiel, ich schrieb das Haskell-Programm zu finden inversen einige einfache Polynomfunktionen:

bijective_function x = x*2+1

main = do
    print $ bijective_function 3
    print $ inverse_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

inverse X = X
inverse (Const a) = Const a
inverse (Plus (Const a) b) = (Subtract (inverse b) (Const a))
inverse (Plus b (Const a)) = inverse (Plus (Const a) b)
inverse (Mult (Const a) b) = (Div (inverse b) (Const a))
inverse (Mult b (Const a)) = inverse (Mult (Const a) b)
inverse (Negate a) = Negate $ inverse a
inverse (Asin x) = Sin $ inverse x
inverse (Acos x) = Cos $ inverse x
inverse (Atan x) = Tan $ inverse x
inverse_function x = with_function inverse x

Dieses Beispiel funktioniert nur mit arithmetischen Ausdrücken, aber es könnte wohl verallgemeinert werden, um die Arbeit mit Listen als auch.