Dans le plus pur langages fonctionnels, est-il un algorithme pour obtenir l'inverse de la fonction?
Dans le plus pur fonctionnel langages comme Haskell, est-il un algorithme pour obtenir l'inverse d'une fonction, (edit) lorsqu'il est bijective? Et est-il une manière spécifique pour programmer la fonction de sorte qu'il est?
- Mathématiquement, il n'est pas faux de dire que, dans le cas de
f x = 1
, à l'inverse de l'1 est un ensemble d'entiers et l'inverse de tout le reste est vide de sens. Indépendamment de ce que certaines réponses-dire, la fonction n'étant pas bijective n'est pas le plus gros problème. - La bonne réponse est OUI, mais il n'est pas efficace. Soit f : A -> B et finie, alors, étant donné b€B, vous "seulement" doit inspecter tous les f(Un) pour trouver tous les euros de l'Un que f(a)=b. Dans un ordinateur quantique, peut-être aurait O(taille(a)) complexité. Bien sûr, vous recherchez un algorithme de pratique. Il n'est pas (a O(2^la taille(un)) ), mais il existe...
- QuickCheck est en train de faire exactement (ils recherchent un " False f : A -> Bool).
- Je suis en désaccord; ce n'est généralement pas ce que l'on entend par inversion. Presque à chaque fois, je rencontre le long terme, à l'inverse de l'
f
est une fonctiong
tels quef . g = id
etg . f = id
. Votre candidat n'a même pas typecheck dans ce cas. - vous avez raison. Ce que j'ai dit est appelée l'inverse de l'image, pas une fonction inverse. Mon point était que les réponses soulignant que
f x = 1
n'a pas d'inverse de prendre une approche étroite et d'ignorer toute la complexité du problème. - un inverse", c'est exactement la même chose que de dire l'inverse de l'image est un singleton.
- C'est une idée fausse commune que les ordinateurs quantiques peut effectuer des opérations de façon exponentielle-nombreuses copies de données en parallèle. Rappelez-vous, la mesure est destructeur, et de mesurer une empêtré valeur produit seulement un classique de la valeur. Holevo du théorème dit que le n qubits peut coder au plus n bits. Et il serait considéré comme très surprenant si les ordinateurs quantiques pourraient résoudre efficacement tous les problèmes NP (plus formellement, nous pensons que NP ⊄ BQP). [suite...]
- Pour le cas spécifique que vous mentionnez—la recherche au travers d'une liste non ordonnée d'éléments, vous souhaitez utiliser l'algorithme de Grover, qui recherche une longueur n de la liste en O(√*n*) de temps sur un ordinateur quantique. Et effectivement, Wikipédia dit que "c'est peut-être plus exact de décrire [Grover algorithme] comme" l'inversion d'une fonction,'" donc là vous allez. Donc, qui donne une équation du second degré speedup: au lieu de O(2^|A|) temps d'inverser une fonction, vous vous retrouvez avec O(2^(|A|/2), le temps, et ne peut pas faire mieux.
- Merci @AntalS-Z, j'ai dit "peut-être aurait" parce que "La relation entre BQP et NP n'est pas connu"
Vous devez vous connecter pour publier un commentaire.
Dans certains cas, oui! Il y a un beau papier appelé Bidirectionalization Gratuitement! qui décrit quelques cas, lorsque votre fonction est assez polymorphe, où il est possible, de manière entièrement automatique pour dériver une fonction inverse. (Il explique également ce qui rend le problème plus difficile lorsque les fonctions ne sont pas polymorphes.)
Ce que vous obtenez dans le cas où votre fonction est inversible est l'inverse (avec une fausse entrée); dans d'autres cas, vous avez une fonction qui tente de "fusion" un vieux de la valeur d'entrée et une nouvelle valeur de sortie.
put
fonctions dans toutes les structures d'enregistrement découlantData
: haskell.org/pipermail/haskell-cafe/2008-April/042193.html en utilisant une approche similaire à celle présentée ultérieurement (avec plus de rigueur, plus généralement, sur le fond, etc.) dans "gratuitement".Non, il n'est pas possible en général.
Preuve: considérons bijective fonctions de type
avec
Supposons que nous avons un onduleur
inv :: F -> F
tels queinv f . f ≡ id
. Dire que nous avons testé pour la fonctionf = id
, en confirmant queDepuis cette première
B0
dans la sortie doit venir après un certain temps fini, nous avons une limite supérieuren
à la fois de la profondeur à laquelleinv
avait réellement évalué notre test d'entrée pour obtenir ce résultat, ainsi que le nombre de fois où il peut avoir appeléf
. Définissons maintenant une famille de fonctionsClairement, pour tous les
0<j≤n
,g j
est une bijection, en fait auto-inverse. Donc, nous devrions être en mesure de confirmermais pour accomplir cela,
inv (g j)
aurait fallu soitg j (B1 : repeat B0)
à une profondeur den+j > n
head $ g j l
pour au moinsn
différentes listes de correspondancereplicate (n+j) B0 ++ B1 : ls
Jusqu'à ce point, au moins l'un des
g j
est impossible de distinguer lesf
, et depuisinv f
n'avait pas fait une de ces évaluations,inv
ne pouvait pas avoir dit à part – court de faire de certains à l'exécution des mesures sur son propre, ce qui n'est possible que dans leIO Monad
.⬜
Vous pouvez le regarder sur wikipedia, il est appelé Réversible Informatique.
En général, vous ne pouvez pas le faire bien et aucun des langages fonctionnels ont cette option. Par exemple:
Cette fonction ne doit pas l'inverse.
f
possède un inverse, c'est juste que l'inverse est une fonction non déterministe?g :: Int -> a
qui est l'inverse def
, même si vous pouvez décrire l'inverse def
mathématiquement.f x = 2 * x
êtref' x = [x / 2]
, et alors l'inverse def _ = 1
estf' 1 = [minBound ..]; f' _ = []
. C'est, il y a beaucoup inverses pour 1, et aucun pour toute autre valeur.Pas dans la plupart des langages fonctionnels, mais dans la logique de la programmation ou de la programmation relationnel, la plupart des fonctions que vous définissez sont en fait pas des fonctions mais des "relations", et ceux-ci peuvent être utilisés dans les deux directions. Voir, par exemple, prolog ou kanren.
Tâches de ce genre sont presque toujours indécidable. Vous pouvez avoir une solution pour certaines fonctions spécifiques, mais pas en général.
Ici, vous ne pouvez même pas reconnaître les fonctions qui ont un inverse. Citant Barendregt, H. P. Le Lambda Calcul: Sa Syntaxe et de la Sémantique. North Holland, Amsterdam (1984):
Prenons Un être à l'ensemble de lambda-termes qui représentent inversible fonctions et B le reste. Les deux sont non-vide et fermé en vertu de la bêta de l'égalité. Il n'est donc pas possible de décider si une fonction est inversible ou non.
(Cela s'applique à la non typée lambda calcul. TBH je ne sais pas si l'argument peut être directement adapté à un lambda calcul typé quand on sait que le type d'une fonction que nous voulons inverser. Mais je suis sûr que ce sera le même.)
Si vous pouvez énumérer le domaine de la fonction et permet de comparer les éléments de la gamme pour l'égalité, vous pouvez vous - assez simple. Par énumérer je veux dire d'avoir une liste de tous les éléments disponibles. Je vais m'en tenir à Haskell, car je ne sais pas Ocaml (ou même comment exploiter correctement 😉
Ce que vous voulez faire est de lancer à travers les éléments du domaine et de voir si ils sont égaux à l'élément de la gamme que vous essayez d'inverser la, et de prendre le premier qui fonctionne:
Puisque vous avez déclaré que
f
est une bijection, il est lié à un et un seul élément. Le truc, bien sûr, est de s'assurer que votre énumération du domaine réellement atteint tous les éléments dans un temps fini. Si vous essayez d'inverser une bijection deInteger
àInteger
, à l'aide de[0,1 ..] ++ [-1,-2 ..]
ne fonctionnera pas tant que vous n'aurez jamais à les nombres négatifs. Concrètement,inv ([0,1 ..] ++ [-1,-2 ..]) (+1) (-3)
ne sera jamais à donner une valeur.Cependant,
0 : concatMap (\x -> [x,-x]) [1..]
de travail, comme cela va à travers les entiers dans l'ordre suivant[0,1,-1,2,-2,3,-3, and so on]
. En effetinv (0 : concatMap (\x -> [x,-x]) [1..]) (+1) (-3)
rapidement retourne-4
!La De contrôle.Monade.Omega paquet peut vous aider à exécuter par le biais de listes de n-uplets, etc dans le bon sens; je suis sûr qu'il y a plus de paquets comme ça - mais je ne les connais pas.
Bien sûr, cette approche est plutôt bas du front et de la force brute, pour ne pas mentionner laide et inefficace! Donc, je vais terminer par quelques remarques sur la dernière partie de votre question, sur la façon de "l'écriture" bijections. Le système de type de Haskell n'est pas à prouver qu'une fonction est une bijection - vous voulez vraiment quelque chose comme Agda pour cela -, mais il est prêt à vous faire confiance.
(Attention: pas testé le code qui suit)
Si vous le pouvez définir un type de données de
Bijection
s entre les typesa
etb
:avec autant de constantes (où vous pouvez dire " je savoir ils sont des bijections!') que vous le souhaitez, tels que:
et un couple de smart combinators, tels que:
Je pense que vous pourriez alors faire
invert (mapBi add1Bi) [1,5,6]
et obtenir[0,4,5]
. Si vous choisissez votre combinators de manière intelligente, je pense que le nombre de fois où vous aurez à écrire unBi
constante à la main pourrait être assez limité.Après tout, si vous connaissez une fonction est une bijection, vous allez, espérons-le, une preuve de l'esquisse de ce fait dans votre tête, ce qui le Curry-Howard isomorphisme doit être capable de se transformer en un programme 🙂
J'ai récemment eu affaire à des questions de ce genre, et non, je dirais que (a) il n'est pas difficile dans de nombreux cas, mais (b) il n'est pas efficace du tout.
Fondamentalement, supposons que vous avez
f :: a -> b
, et quef
est en effet un bjiection. Vous pouvez calculer l'inverse de laf' :: b -> a
dans un vraiment stupide façon:Si
f
est une bijection etenumerate
vraiment produit de toutes les valeurs dea
, alors vous allez finir par frapper una
tels quef a == b
.Des Types qui ont un
Bounded
et unEnum
instance peut être trivialement faitRecursivelyEnumerable
. Paires deEnumerable
types peuvent également être faiteEnumerable
:En va de même pour les disjonctions de
Enumerable
types:Le fait que l'on peut faire à la fois pour
(,)
etEither
signifie probablement que nous pouvons le faire pour n'importe quel type de données algébrique.Pas chaque fonction a un inverse. Si vous limiter le débat à un-à-un les fonctions, la possibilité d'inverser une fonction arbitraire de subventions de la capacité à faire craquer n'importe quel système cryptographique. Nous avons, en quelque sorte, de l'espoir ce n'est pas faisable, même dans la théorie!
String encrypt(String key, String text)
sans la clé, vous ne serez pas en mesure de faire quoi que ce soit. EDIT: en Plus de ce delnan dit.Non, pas toutes les fonctions inverses. Par exemple, ce qui serait l'inverse de cette fonction?
Dans certains cas, il est possible de trouver l'inverse d'une fonction bijective et à la convertir en une représentation symbolique. Basé sur cet exemple, j'ai écrit ce Haskell programme pour trouver l'inverse de certains de simples fonctions polynomiales:
Cet exemple ne fonctionne qu'avec des expressions arithmétiques, mais il pourrait probablement être généralisée à travailler avec des listes ainsi.