Czy w językach funkcjonalnych istnieje algorytm do uzyskania funkcji odwrotnej?

100

Czy w czysto funkcjonalnych językach, takich jak Haskell, istnieje algorytm uzyskiwania odwrotności funkcji (edytuj), gdy jest ona bijektywna? Czy istnieje konkretny sposób zaprogramowania funkcji?

MaiaVictor
źródło
5
Z matematycznego punktu widzenia nie jest błędne stwierdzenie, że w przypadku f x = 1odwrotności 1 jest zbiorem liczb całkowitych, a odwrotnością czegokolwiek innego jest zbiorem pustym. Niezależnie od tego, co mówią niektóre odpowiedzi, funkcja, która nie jest bijektywna, nie jest największym problemem.
Karolis Juodelė
2
Prawidłowa odpowiedź to TAK, ale nie jest wydajna. Niech f: A -> B i A są skończone, więc biorąc pod uwagę b € B, musisz „tylko” sprawdzić wszystkie f (A), aby znaleźć wszystkie a € A, które f (a) = b. W komputerze kwantowym prawdopodobnie miałby złożoność O (rozmiar (a)). Oczywiście szukasz praktycznego algorytmu. To nie jest (ma O (2 ^ rozmiar (a))), ale istnieje ...
josejuan
QuickCheck robi to dokładnie (szukają fałszu w f: A -> Bool).
josejuan
4
@ KarolisJuodelė: Nie zgadzam się; to zwykle nie oznacza odwrotności. Prawie za każdym razem, gdy napotykam ten termin, odwrotność funkcji fjest gtaka, że f . g = idi g . f = id. W takim przypadku Twój kandydat nawet nie sprawdza maszynopisu.
Ben Millwood,
3
@BenMillwood, masz rację. To, co powiedziałem, nazywa się odwrotnym obrazem, a nie funkcją odwrotną. Chodziło mi o to, że odpowiedzi wskazujące, że f x = 1nie ma odwrotności, przyjmują bardzo wąskie podejście i ignorują całą złożoność problemu.
Karolis Juodelė

Odpowiedzi:

101

W niektórych przypadkach tak! Jest piękny artykuł zatytułowany Dwukierunkowość za darmo!który omawia kilka przypadków - kiedy twoja funkcja jest wystarczająco polimorficzna - w których możliwe jest, całkowicie automatycznie, wyprowadzenie funkcji odwrotnej. (Omawia również, co utrudnia problem, gdy funkcje nie są polimorficzne).

To, co otrzymujesz w przypadku, gdy twoja funkcja jest odwracalna, jest odwrotnością (z fałszywymi danymi wejściowymi); w innych przypadkach otrzymujesz funkcję, która próbuje "scalić" starą wartość wejściową i nową wartość wyjściową.

Daniel Wagner
źródło
3
Oto nowszy artykuł, w którym dokonano przeglądu stanu techniki w dziedzinie dwukierunkowości. Obejmuje trzy rodziny technik, w tym podejście „syntaktyczne” i oparte na kombinatorach: iai.uni-bonn.de/~jv/ssgip-bidirectional-final.pdf
sclv
I żeby wspomnieć, w 2008 roku pojawiła się wiadomość do -cafe, ze złym hackiem do odwracania putfunkcji w dowolne struktury rekordów Data: haskell.org/pipermail/haskell-cafe/2008-April/042193.html przy użyciu podejścia podobnego do który później przedstawił (bardziej rygorystycznie, bardziej ogólnie, bardziej pryncypialny itp.) w „za darmo”.
sclv
Jest rok 2017 i oczywiście link do artykułu nie jest już ważny. Tutaj jest zaktualizowany: pdfs.semanticscholar.org/5f0d/ ...
Mina Gabriel
37

Nie, generalnie nie jest to możliwe.

Dowód: rozważ bijektywne funkcje typu

type F = [Bit] -> [Bit]

z

data Bit = B0 | B1

Załóżmy, że mamy falownik inv :: F -> Ftakie, że inv f . f ≡ id. Powiedzmy, że przetestowaliśmy to pod kątem funkcji f = id, potwierdzając to

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

Ponieważ to pierwsze B0dane wyjściowe musiało nastąpić po pewnym skończonym czasie, mamy górną granicę nzarówno dla głębokości, do której invfaktycznie oszacowaliśmy nasze dane wejściowe testu, aby uzyskać ten wynik, jak i ile razy można było wywołać f. Zdefiniuj teraz rodzinę funkcji

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

Oczywiście, dla wszystkich 0<j≤n, g jto bijection w rzeczywistości samodzielnego odwrotności. Więc powinniśmy być w stanie to potwierdzić

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

ale aby to spełnić, inv (g j)musiałby to zrobić

  • ocenić g j (B1 : repeat B0)do głębokościn+j > n
  • oceniać head $ g j lco najmniej nróżne pasujące listyreplicate (n+j) B0 ++ B1 : ls

Do tego momentu co najmniej jeden z nich g jjest nie do odróżnienia od f, a ponieważ inv fnie wykonał żadnej z tych ocen, invnie mógł go rozróżnić - pomijając wykonanie samodzielnych pomiarów w czasie wykonywania, co jest możliwe tylko w IO Monad.

                                                                                                                                   ⬜

leftaroundabout
źródło
19

Możesz to sprawdzić na Wikipedii, nazywa się Reversible Computing .

Generalnie jednak nie możesz tego zrobić i żaden z języków funkcjonalnych nie ma takiej możliwości. Na przykład:

f :: a -> Int
f _ = 1

Ta funkcja nie ma odwrotności.

mck
źródło
1
Czy nie byłoby błędem powiedzieć, że fma odwrotność, po prostu odwrotność jest funkcją niedeterministyczną?
Matt Fenwick
10
@MattFenwick Na przykład w językach takich jak Haskell funkcje po prostu nie są niedeterministyczne (bez zmiany typów i sposobu ich używania). Nie istnieje żadna funkcja Haskella, g :: Int -> aktóra byłaby odwrotnością f, nawet jeśli można opisać odwrotność fmatematycznie.
Ben
2
@Matt: Szukaj „dołu” w programowaniu funkcjonalnym i logice. „Dno” jest wartością „niemożliwą”, ponieważ jest sprzeczne, nierozstrzygalne lub stanowi rozwiązanie nierozstrzygalnego problemu (jest to więcej niż tylko sprzeczność - możemy metodycznie „gonić” za rozwiązaniem podczas eksploracji projektu spacja przy użyciu „undefined” i „error” podczas programowania). „Dół” x ma typ a. „Zamieszkuje” (lub jest „wartością”) każdego typu. Jest to logiczna sprzeczność, ponieważ typy są zdaniami i nie ma wartości, która spełniałaby każde zdanie. Poszukaj dobrych dyskusji w Haskell-Cafe
nomen
2
@Matt: Zamiast charakteryzować nieistnienie odwrotności w kategoriach niedeterminizmu, należy scharakteryzować je w kategoriach dna. Odwrotność f _ = 1 jest dolna, ponieważ musi obejmować każdy typ (alternatywnie jest dolna, ponieważ f nie ma funkcji odwrotnej dla żadnego typu z więcej niż jednym elementem - myślę, że aspekt, na którym się skupiłeś). Bycie na dole można traktować zarówno pozytywnie, jak i negatywnie, jako twierdzenia o wartościach. Można rozsądnie mówić o odwrotności dowolnej funkcji jako o dnie „wartości”. (Chociaż nie jest to „naprawdę” wartość)
nomen
1
Wróciwszy tutaj dużo później, myślę, że rozumiem, do czego zmierza Matt: często modelujemy niedeterminizm za pomocą list i moglibyśmy zrobić to samo z odwrotnością. Niech odwrotność f x = 2 * xbędzie f' x = [x / 2], a potem odwrotność f _ = 1jest f' 1 = [minBound ..]; f' _ = []. Oznacza to, że istnieje wiele odwrotności dla 1 i żadnych dla innych wartości.
amalloy
16

Nie w większości języków funkcyjnych, ale w programowaniu logicznym lub relacyjnym, większość funkcji, które definiujesz, nie jest w rzeczywistości funkcjami, ale „relacjami”, które mogą być używane w obu kierunkach. Zobacz na przykład prolog lub kanren.

amaloy
źródło
1
Albo Merkury , który poza tym ma wiele wspólnego z duchem Haskella. - Słuszna uwaga, +1.
leftaround około
11

Takie zadania są prawie zawsze nierozstrzygalne. Możesz mieć rozwiązanie dla niektórych konkretnych funkcji, ale nie ogólnie.

Tutaj nie można nawet rozpoznać, które funkcje mają odwrotność. Cytując Barendregt, HP. Rachunek lambda: jego składnia i semantyka. Holandia Północna, Amsterdam (1984) :

Zbiór warunków lambda nie jest trywialny, jeśli nie jest ani pusty, ani pełny. Jeśli A i B są dwoma nietrywialnymi, rozłącznymi zbiorami wyrażeń lambda zamkniętych pod (beta) równością, to A i B są rekursywnie nierozłączne.

Przyjmijmy, że A będzie zbiorem wyrażeń lambda, które reprezentują funkcje odwracalne, a B resztę. Obie są niepuste i zamknięte w ramach równości beta. Nie można więc zdecydować, czy funkcja jest odwracalna, czy nie.

(Odnosi się to do rachunku lambda bez typu. TBH Nie wiem, czy argument można bezpośrednio dostosować do rachunku lambda o typie, gdy znamy typ funkcji, którą chcemy odwrócić. Ale jestem prawie pewien, że będzie to podobny.)

Petr Pudlák
źródło
11

Jeśli potrafisz wyliczyć dziedzinę funkcji i możesz porównać elementy zakresu pod kątem równości, możesz - w dość prosty sposób. Przez wyliczenie mam na myśli posiadanie listy wszystkich dostępnych elementów. Zostanę przy Haskellu, bo nie znam Ocamla (ani nawet jak go odpowiednio skapitalizować ;-)

To, co chcesz zrobić, to przejrzeć elementy domeny i sprawdzić, czy są one równe elementowi zakresu, który próbujesz odwrócić, i wybrać pierwszy, który działa:

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

Ponieważ stwierdziłeś, że fjest to bijekcja, musi istnieć jeden i tylko jeden taki element. Rzecz w tym, by upewnić się, że wyliczenie domeny faktycznie dotrze do wszystkich elementów w określonym czasie . Jeśli próbujesz odwrócić bijekcję od Integerdo Integer, użycie [0,1 ..] ++ [-1,-2 ..]nie zadziała, ponieważ nigdy nie dojdziesz do liczb ujemnych. A konkretnie, inv ([0,1 ..] ++ [-1,-2 ..]) (+1) (-3)nigdy nie przyniesie wartości.

Jednak 0 : concatMap (\x -> [x,-x]) [1..]zadziała, ponieważ przebiega przez liczby całkowite w następującej kolejności [0,1,-1,2,-2,3,-3, and so on]. Rzeczywiście, inv (0 : concatMap (\x -> [x,-x]) [1..]) (+1) (-3)szybko wraca -4!

Control.Monad.Omega pakiet może pomóc uruchomić poprzez list krotki etcetera w dobrym tego słowa znaczeniu; Jestem pewien, że takich pakietów jest więcej - ale ich nie znam.


Oczywiście to podejście jest raczej powściągliwe i brutalne, nie wspominając o brzydkim i nieefektywnym! Więc zakończę kilkoma uwagami na temat ostatniej części twojego pytania, jak „pisać” bijezje. System typów Haskella nie jest w stanie udowodnić, że funkcja jest bijection - naprawdę chcesz do tego czegoś takiego jak Agda - ale chce ci zaufać.

(Ostrzeżenie: następuje nieprzetestowany kod)

Czy możesz więc zdefiniować typ danych Bijections między typami aa b:

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

wraz z tyloma stałymi (gdzie możesz powiedzieć „ Wiem, że to bijekty!”), ile chcesz, na przykład:

notBi :: Bi Bool Bool
notBi = Bi not not

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

i kilka inteligentnych kombinatorów, takich jak:

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)

Myślę, że mógłbyś wtedy zrobić invert (mapBi add1Bi) [1,5,6]i dostać [0,4,5]. Jeśli mądrze wybierzesz kombinatory, myślę, że ile razy będziesz musiał napisaćBi ręcznie stałą, może być dość ograniczona.

W końcu, jeśli wiesz, że funkcja jest bijection, miejmy nadzieję, że będziesz miał w głowie szkic dowodowy tego faktu, który izomorfizm Curry-Howarda powinien być w stanie przekształcić w program :-)

yatima2975
źródło
6

Ostatnio miałem do czynienia z takimi problemami i nie, powiedziałbym, że (a) w wielu przypadkach nie jest to trudne, ale (b) w ogóle nie jest wydajne.

Zasadniczo załóżmy, że tak f :: a -> b, i fto rzeczywiście jest różnica. Możesz obliczyć odwrotność f' :: b -> aw naprawdę głupi sposób:

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

Jeśli fjest bijekcją i enumeratenaprawdę wytwarza wszystkie wartości a, to w końcu trafisz na atakie, żef a == b .

Typy, które mają a Boundedi Enuminstancję, można w trywialny sposób tworzyć RecursivelyEnumerable. EnumerableMożna również tworzyć pary typów 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

To samo dotyczy rozłączeń Enumerabletypów:

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

Fakt, że możemy to zrobić zarówno dla, jak (,)i Eitherprawdopodobnie oznacza, że ​​możemy to zrobić dla dowolnego algebraicznego typu danych.

Luis Casillas
źródło
5

Nie każda funkcja ma odwrotność. Jeśli ograniczysz dyskusję do funkcji jeden do jednego, możliwość odwrócenia dowolnej funkcji daje możliwość złamania dowolnego kryptosystemu. Musimy mieć nadzieję, że nie jest to wykonalne, nawet w teorii!

Jeffrey Scofield
źródło
13
Każdy kryptosystem (z wyjątkiem kilku nieparzystych, takich jak jednorazowe podkładki, które są niewykonalne z innych powodów) może zostać złamany przez brutalną siłę. To nie czyni ich mniej użytecznymi, ani też nie byłaby niepraktycznie kosztowną funkcją inwersji.
Naprawdę? Jeśli myślisz o funkcji szyfrowania String encrypt(String key, String text)bez klucza, nadal nie będziesz w stanie nic zrobić. EDYCJA: Plus to, co powiedział Delnan.
mck
@MaciekAlbin Zależy od Twojego modelu ataku. Na przykład wybrane ataki w postaci jawnego tekstu mogą pozwolić na wyodrębnienie klucza, co umożliwiłoby następnie atakowanie innych zaszyfrowanych tekstów zaszyfrowanych tym kluczem.
Przez „wykonalne” miałem na myśli coś, co można zrobić w rozsądnym czasie. Nie miałem na myśli „obliczalnego” (jestem prawie pewien).
Jeffrey Scofield
@JeffreyScofield Rozumiem, o co chodzi. Ale muszę powiedzieć, że jestem zdezorientowany „wykonalnością teoretyczną” - czy (nasza definicja) wykonalności nie odnosi się tylko do tego, jak trudno jest to zrobić w praktyce?
5

W niektórych przypadkach można znaleźć odwrotność funkcji bijektywnej, przekształcając ją w reprezentację symboliczną. Na podstawie tego przykładu napisałem ten program Haskella, aby znaleźć odwrotności niektórych prostych funkcji wielomianowych:

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

Ten przykład działa tylko z wyrażeniami arytmetycznymi, ale prawdopodobnie można go uogólnić, aby działał również z listami.

Anderson Green
źródło
4

Nie, nie wszystkie funkcje mają nawet odwrotności. Na przykład, jaka byłaby odwrotność tej funkcji?

f x = 1
Dirk Holsopple
źródło
Twoja funkcja jest stałą, tutaj chodzi o funkcje bijektywne.
Soleil - Mathieu Prévot