Discussion :

[guipe]

Bonjour je viens de débuter le langage CAML, c'est un peu difficile pour l'instant.

Mon but est de définir une fonction qui prend un entier en argument et retourne l'entier de Church correspondant.

ex : fonction 0 retourne x
fonction 1 retourne f x
fonction 2 retourne f(f x) ....


Voici ce que j'ai fait( ça ne fonctionne pas)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let rec int2church n = 
           if (n = 0) then (fun f x -> x)
            else (fun f x -> int2church(n-1));;

Voici l'erreur retournée :

This expression has type int -> 'a -> int -> int,
but is used with type int -> int.


Merci de votre aide !

[TropMDR]

ex : fonction 0 retourne x
fonction 1 retourne f x
fonction 2 retourne f(f x) ....

Essaye de donner une définition récursive en français d'abord, puis implémente la. C'est à dire "quelle est la définition au rang n en fonction de la définition au rang (n - 1)". Tu verras, ça passera tout seul

[guipe]

Au rang n ma fonction doit renvoyer f ^ n( f puissance n) x.

[TropMDR]

Cherche une définition récursive, c'est à dire une définition où la valeur au rang n est défini au rang (n - 1).

Si tu as des cours de caml, tu as du en voir un certain nombre. Par exemple on pourrait dire que

x + 0 = x
x + (n +1) = (x + n) + 1

ou encore
x * 0 = 0
x * (n + 1) = (x * n) + x

(premier exercice : passer ces définitions en caml)

Tu vois dans les deux cas, il y a une partie de la définition qui est "complète" (la première ligne), c'est à dire que la définition de + 0 ne fait pas appelle à + et la définition de * 0 ne fait pas appelle à *. C'est ce qu'on appelle la condition d'arrêt.
Il y a ensuite une partie de la définition qui est récursive, parce que la définition de + dépend de... la définition de + ! Ca pourrait paraitre bizarre, mais c'est "bien fondé" (comprendre "correct") parce que c'est la définition de + (n +1) qui dépend de la définition de + n. Donc par exemple la définition de +3 dépend de la définition de +2 qui dépend de celle de +1 qui dépend de celle de +0 qui... est bien définie ! Donc c'est bon.

Maintenant, essaye d'écrire le même genre de définition pour "e2c" :

e2c 0 f x = ??
e2c (n + 1) f x = ??

puis tu n'a plus qu'à traduire ça en caml !


(PS: les lecteurs observateurs auront noté que dans la définition de +, il faut quand même être capable d'avoir le (+ 1). C'est l'opération "successeur" que l'ont suppose ici disponible)

[guipe]

e2c 0 f x = x
e2c (n + 1) f x = n f x * 1 f x

[TropMDR]

e2c 0 f x = x
e2c (n + 1) f x = n f x * 1 f x

C'est bizarre, dans le cas n+1, ta définition de e2c ne dépend pas de e2c. Et essaye pour n = 0 et n = 1 par exemple, pour voir si ça correspond à ce que tu veux

[guipe]

En effet n'importe quoi.

Ce serait plutôt e2c (n + 1) f x = ec2 n f x * f

[asefthukom]

Ce serait plutôt e2c (n + 1) f x = ec2 n f x * f

Je pense que tu as voulu dire :

e2c (n + 1) f x = ec2 n f (f x)

(sauf si c'est une convention d'écriture que tu as choisi, dans ce cas pardon)

[guipe]

Oui voilà !

[guipe]

Bref au rang n au final ça me donne :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
let rec int2church n f x= if(n=0) then x
                                            else int2church (n-1) f (f x)

Maintenant je dois faire la fonction qui "convertit" un entier de church en entier !

[gasche]

L'entier de church pour n correspond à la fonction qui à f renvoie f^n, f appliquée n fois. Il y a une fonction très simple qui, appliquée n fois à un argument très simple donne n. Tu n'as pas une idée ?

Indice : l'argument auquel il faut appliquer cette fonction est 0.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

let church2int church_n = church_n (...) 0

[guipe]

La fonction identité ?

let identite x = x;

ou

let identite= fun x-> x ;

[gasche]

Si tu appliques n fois l'identité à 0 (pour n=3 on parle bien de (id (id (id 0)))), ça reste 0.

[guipe]

Je vois pas !

[gasche]

Un petit effort...

Voici les équations satisfaites par la fonction "f" qu'il convient de donner à tes entiers de church :
0 = 0 (appliquée 0 fois, on obtient 0)
f(0) = 1 (appliquée 1 fois, on obtient 1)
f(f(0)) = 2 (appliquée 2 fois (entier de church 2), on obtient 2)
f(f(f(0)))) = 3
...

Aucune idée de fonction 'f' qui convient ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
let f = ...
let church2int church_n = church_n f 0

[guipe]

La fonction successeur ?

[TropMDR]

Oui, cette fois ci, c'est la bonne !

Mais sérieusement, quand tu proposes une solution, essaye au moins sur n = 0, 1 et 2 ! Je ne dis pas qu'il faut que tu prouves tout de suite toutes tes réponses, mais le minimum, c'est de faire un "test unitaires" sur deux ou trois valeurs !

Un jour, tu seras amené à programmer de vraies choses, et tu n'auras pas un "oracle" (en l'occurrence dvp.net) pour te dire "oui" ou "non" à chacune de tes propositions aléatoire ! Il faudra que tu arrives à te convaincre toi même de la correction de tes propositions...

Je ne dis pas ça pour t'agresser, juste pour t'aider à progresser

(personnellement, j'ai tellement peu confiance en mes aptitudes de programmation que je prouve tous mes programmes )

Bon courage pour la suite

[guipe]

Oui j'ai du mal à démontrer en fait.

Car quand on applique un entier de church à la fonction successeur, on va obtenir l'entier de church initial + 1 non ?

[guipe]

C'est bon je crois que j'ai compris.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

L'entier de church pour n correspond à la fonction qui à f renvoie f^n, f appliquée n fois

J'ai fait la démo sur papier et j'ai bien ça.

Merci beaucoup !