Quel est le nom de cette généralisation de idempotence?
-
27-10-2019 - |
Question
Beaucoup de propriétés généralement de fonctions utiles ont des noms concis. Par exemple, associativité , commutativity , transitivité , etc.
Je fais une bibliothèque pour une utilisation avec QuickCheck qui fournit des définitions abrégées de ces propriétés et d'autres .
Celui que j'ai une question sur est idempotence des fonctions unaires. Une fonction f est idempotente iif Ux. f x == f (f x).
Il y a une généralisation intéressante de cette propriété pour laquelle je me bats pour trouver un nom de la même concise. Pour éviter de biaiser les choix de nom de peuples en proposant un, je le nomme P et fournir la définition suivante:
Une fonction f a la propriété de P par rapport à g iif Ux. f x == f (g x). On peut le voir comme une généralisation de idempotence en redéfinissant idempotence en termes de P. Une fonction f est idempotent ssi il a la propriété P par rapport à lui-même.
Pour voir que c'est une propriété utile d'observer qu'il justifie une règle de réécriture qui peut être utilisé pour mettre en œuvre un certain nombre d'optimisations communes. Cela se produit souvent, mais pas toujours quand g est une sorte de fonction canonicalisation. Voici quelques exemples:
-
length
P par rapport àmap
f
(pour tous les choix de f) - Conversion en CNF est P par rapport à la conversion en de DNF (et vice versa)
- normalisation Unicode pour former NFC est P par rapport à la normalisation pour former NFD (et vice-versa)
-
minimum
P par rapport à nub
Que voulez-vous nommer cette propriété?
La solution
On peut dire que map f
est length
-préservation, ou que length
est invariante par map f
ing. Alors que diriez-vous:
- g est f-préservation.
- f est invariante (application) g.