Comment mettre en œuvre f (g) == g (f)

Question

Je answered a question yesterday et il a obtenu mon esprit à penser à un intéressant (pour moi) Casse-tête

Avec la restriction de l'utilisation lambdas, des chiffres et + seulement (pas if, ?:, ou d'autres caractéristiques linguistiques), l'objectif est de mettre en œuvre certaines f et certains g tels que

// contract 
f(x) => f' 
g(y) => g' 
f'(g') == g'(f') 

// or more simply: 
m(n) == n(m) 

Voici ce que je suis venu avec à ce jour - ce code est en J avascript dans le but d'être en mesure de démontrer le code dans le navigateur mais les réponses dans une langue quelconque fonctionnelle sont acceptables (raquette, clojure, ocaml, lambda calc, etc)

// f 
 
const f = x => k => 
 
    k(y => y + x) 
 

 
// g 
 
const g = y => k => 
 
    k(x => x + y) 
 
    
 
// make instance of each 
 
const a = f(1) 
 
const b = g(2) 
 

 
console.log(a(b)) 
 
// x => x + y1 
 
// should be 3 
 

 
console.log(b(a)) 
 
// y => y + x2 
 
// should be 3

J'ai été en mesure de fixer un la moitié de la relation, mais l'autre côté reste brisé en raison de f et g étant maintenant asymétrique

// f 
 
const f = x => k => 
 
    k(y => y(x)) 
 

 
// g 
 
const g = y => k => 
 
    k(x => x + y) 
 
    
 
// make instance of each 
 
const a = f(1) 
 
const b = g(2) 
 

 
console.log(a(b)) 
 
// 3 
 
// should be 3 (OK) 
 

 
console.log(b(a)) 
 
// y => y + x2 
 
// should be 3

Je sais pourquoi cela ne fonctionne pas, mais je vais avoir du mal à essayer de le réparer. Plus important encore, si ce n'est pas possible, j'aimerais savoir pourquoi.

Si vous venez avec une solution qui brise les restrictions, je suis toujours intéressé à le voir^_^

Answer 1

Cette réponse suppose un système solide de type non-unitaire (par ex. Haskell, mais j'essaie de m'en tenir à la syntaxe JS-like ici). Si nous restons dans le domaine de la paramétrisation, nous n'avons pas besoin (et ne pouvons même pas utiliser) de nombres ou de conditions. Les fonctions constantes ne changent rien, donc je vais les laisser et traiter directement f et g.

D'abord, observer que l'équation

f(g) == g(f) 

implique que les deux f et g ont des types de fonction. En supposant que les deux ont des entrées différentes, nous obtenons que f: A -> X et g: B -> X == (A -> X) -> X == ((B -> X) -> X) -> X == ..., c'est à dire, vous obtenez un type infini.Je me souviens avoir lu un article sur cette construction exacte (on peut la représenter comme une paire de types, et je pense que cela forme une catégorie), mais j'ai malheureusement oublié son nom - peut-être y a-t-il plus à dire ici.

Une solution plus simple consisterait à exiger A == B. Puis f, g: A -> X, mais depuis X == A par l'équation de symétrie, il s'ensuit que f, g: A -> A - pour arbitraire A, c'est. Un possibilitity remplir c'est la fonction d'identité:

id(id) == id(id) 

Les autres solutions se posent lorsque nous sommes spécialistes de A-A -> A; alors nous cherchons des fonctions de type (A -> A) -> (A -> A). Ce sont, pour une, la fonction d'identité (spécialisée), qui a déjà été trouvé, mais aussi toutes les fonctions de la forme h => h o ... o h - compositions ((o) = h => x => h(h(x))) d'une fonction pour un certain nombre de types. Ceux-ci "ajoutent leurs répétitions" sur demande, par ex.

(h => h o h)(h => h o h) == (h => h o h) o (h => h o h) 
         == h => h o h o h o h. 

De là, nous voyons que nous pouvons choisir

f == g == h => h, 
f == g == h => h o h, 
f == g == h => h o h o h, 
f == g == ... 

qui sont, je pense, toutes les fonctions de type forall A. (A -> A) -> (A -> A) (hors nontermination).

Il semble aussi y avoir une relation de la limite de cette construction (composition infinie) au cas infini mentined ci-dessus (maintenant en temps réel Haskell):

Prelude> let g = \h -> h . g 

<interactive>:11:19: 
    Occurs check: cannot construct the infinite type: b ~ (b -> c) -> c 

Answer 2

C'est le plus proche que je suis en mesure d'obtenir, mais il utilise une ternaire (?:) expression

const f = x => g => 
 
    g === undefined ? x : g() + x 
 
    
 
const g = y => f => 
 
    f === undefined ? y : f() + y 
 

 
const a = f(1) 
 
const b = g(2) 
 

 
console.log(a(b)) // 3 
 
console.log(b(a)) // 3

ici f est tout à fait équivalent à g et nous pourrions facilement simplement utiliser l'un ou l'autre

const f = x => g => 
 
    g === undefined ? x : g() + x 
 

 
const a = f(1) 
 
const b = f(2) 
 

 
console.log(a(b)) // 3 
 
console.log(b(a)) // 3

Answer 3

Pour que cela se produise évidemment à la fois f et g doit accepter une fonction en tant qu'argument et renvoyer une même valeur de type. Cependant, après avoir bricolé un peu, il me semble que j'ai affaire à des types infinis.

À moins que vos fonctions soient id de Haskell comme x => x de JS. Donc, à Haskell je ferais;

f :: a -> a 
g :: a -> a 

f = id 
g = id 

*Main> f(g)(+3) 2 
5 
*Main> g(f)(+3) 2 
5 

Peut également être implémenté dans JS.