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?
haskell
clojure
functional-programming
ocaml
MaiaVictor
źródło
źródło
f x = 1
odwrotnoś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.f
jestg
taka, żef . g = id
ig . f = id
. W takim przypadku Twój kandydat nawet nie sprawdza maszynopisu.f x = 1
nie ma odwrotności, przyjmują bardzo wąskie podejście i ignorują całą złożoność problemu.Odpowiedzi:
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ą.
źródło
put
funkcji w dowolne struktury rekordówData
: 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”.Nie, generalnie nie jest to możliwe.
Dowód: rozważ bijektywne funkcje typu
z
Załóżmy, że mamy falownik
inv :: F -> F
takie, żeinv f . f ≡ id
. Powiedzmy, że przetestowaliśmy to pod kątem funkcjif = id
, potwierdzając toPonieważ to pierwsze
B0
dane wyjściowe musiało nastąpić po pewnym skończonym czasie, mamy górną granicęn
zarówno dla głębokości, do którejinv
faktycznie 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ę funkcjiOczywiście, dla wszystkich
0<j≤n
,g j
to bijection w rzeczywistości samodzielnego odwrotności. Więc powinniśmy być w stanie to potwierdzićale aby to spełnić,
inv (g j)
musiałby to zrobićg j (B1 : repeat B0)
do głębokościn+j > n
head $ g j l
co najmniejn
różne pasujące listyreplicate (n+j) B0 ++ B1 : ls
Do tego momentu co najmniej jeden z nich
g j
jest nie do odróżnienia odf
, a ponieważinv f
nie wykonał żadnej z tych ocen,inv
nie mógł go rozróżnić - pomijając wykonanie samodzielnych pomiarów w czasie wykonywania, co jest możliwe tylko wIO Monad
.⬜
źródło
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:
Ta funkcja nie ma odwrotności.
źródło
f
ma odwrotność, po prostu odwrotność jest funkcją niedeterministyczną?g :: Int -> a
która byłaby odwrotnościąf
, nawet jeśli można opisać odwrotnośćf
matematycznie.f x = 2 * x
będzief' x = [x / 2]
, a potem odwrotnośćf _ = 1
jestf' 1 = [minBound ..]; f' _ = []
. Oznacza to, że istnieje wiele odwrotności dla 1 i żadnych dla innych wartoś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.
źródło
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) :
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.)
źródło
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:
Ponieważ stwierdziłeś, że
f
jest 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ę odInteger
doInteger
, 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
Bijection
s między typamia
ab
:wraz z tyloma stałymi (gdzie możesz powiedzieć „ Wiem, że to bijekty!”), ile chcesz, na przykład:
i kilka inteligentnych kombinatorów, takich jak:
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 :-)
źródło
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
, if
to rzeczywiście jest różnica. Możesz obliczyć odwrotnośćf' :: b -> a
w naprawdę głupi sposób:Jeśli
f
jest bijekcją ienumerate
naprawdę wytwarza wszystkie wartościa
, to w końcu trafisz naa
takie, żef a == b
.Typy, które mają a
Bounded
iEnum
instancję, można w trywialny sposób tworzyćRecursivelyEnumerable
.Enumerable
Można również tworzyć pary typówEnumerable
:To samo dotyczy rozłączeń
Enumerable
typów:Fakt, że możemy to zrobić zarówno dla, jak
(,)
iEither
prawdopodobnie oznacza, że możemy to zrobić dla dowolnego algebraicznego typu danych.źródło
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!
źródło
String encrypt(String key, String text)
bez klucza, nadal nie będziesz w stanie nic zrobić. EDYCJA: Plus to, co powiedział Delnan.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:
Ten przykład działa tylko z wyrażeniami arytmetycznymi, ale prawdopodobnie można go uogólnić, aby działał również z listami.
źródło
Nie, nie wszystkie funkcje mają nawet odwrotności. Na przykład, jaka byłaby odwrotność tej funkcji?
źródło