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

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?

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

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.

                                                                                                                                   ⬜

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.

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.

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

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

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.

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!

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.

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

f x = 1