Discussion :

[ladeb]

Bonjour à tous!
Je suis étudiante en Licence informatique. Malheureusement, je dois aller au rattrapage en septembre. Mon problème principal est la programmation fonctionnelle. Ce n'est pas du tout ma matière préférée mais il faut s'y coller!

Alors, je suis au début de mes révisions et je bloque un peu sur ce genre d'exercices:
Donner des expressions Caml qui correspondent aux types suivants:

Code :

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

1
2
3
4
5
6
7
 
int->int->int
int->int->int->int
int->(int->int)
int->(int->int)->int
int->(int->int->int)
(int->int)->int->int

Alors moi je bloque quand il y a des parenthèses, ou quand il y a trop de "int", je ne vois pas quelle forme va prendre la fonction.
Si quelqu'un veut bien m'expliquer clairement les démarches pour répondre à cet exo ou si quelqu'un a un tuto ou un cours? J'ai regardé un peu dans les cours, mais je n'ai pas trouvé.

Merci d'avance
Déborah

[InOCamlWeTrust]

Pour comprendre ceci, tu dois d'abord comprendre la flèche.

La flèche est uniquement associative à droite : a -> b -> c signifie a -> (b -> c).

Décompose chaque expression et tu arriveras sans mal à trouver un exemple.

Si on te demande, par exemple, int -> int -> int, c'est pour insister sur le fait que la fonction possède deux arguments. Un exemple serait...

Code :

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

1
2
 
let f a b = a + b

Si on avait voulu une fonction à un argument retournant une nouvelle fonction à un argument, on aurait écrit int -> (int -> int). Entre autres, on aurait pu proposer...

Code :

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

1
2
3
4
5
6
 
let f n =
  if n > 0 then
    (+) 2
  else
    (+) 6

[gasche]

Une bonne méthode pour résoudre ces exercices facilement est de commencer par les parties "sans parenthèses" : le type de fin, à droite de la dernière flèche, est le type de retour, les autres sont les types des paramètres.

Par exemple si tu veux une fonction de la forme "a -> b -> c -> d", tu vas écrire "let f x y z = ...", en t'assurant que x est de type a, y de type b, z de type c, et que tu renvoies le type d.

Concrètement, comment forcer les variables à être d'un type précis ? En utilisant des opérations de ce type dessus. Si tu écris par exemple "let f x = if x = 1 then x else x", tu as comparé x avec un entier, donc le type de x est forcément "int", et tu renvoies toujours x donc le type de retour est encore "int" (tu peux aussi utiliser des additions et renvoyer un entier, mais tu n'auras pas ces possibilités pour tous les types).

La partie délicate concerne les parenthèses : elles désignent le type d'une fonction, qui est soit l'un des paramètres, soit la valeur de retour. Pour obtenir le type d'une fonction en valeur de retour, c'est facile, tu fais comme pour résoudre l'exercice globalement : si tu as int -> (int -> int -> int) par exemple, tu dois écrire

Code :

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

let f n = ...

Mais n doit être un entier, et tu dois renvoyer une fonction de type (int -> int -> int) donc avec deux paramètres et une valeur de retour :

Code :

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

1
2
3
let f n =
  let g a b = if a = 0 && b = 0 then a else a
  if n = 0 then g else g

Quand les types fonctionnels doivent apparaître parmis les paramètres, c'est un peu plus compliqué : au lieu de construire la fonction toi-même (comme g ici) tu dois l'"utiliser" puisqu'elle t'es passée en paramètre. Pour la forcer à avoir le bon type, tu dois lui donner le bon nombre de paramètres, du type demandé, et forcer sa valeur de retour à être du bon type. Pour "int -> (int -> int -> int) -> int" par exemple :

Code :

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

let f x g = ...

Ici x sera "int" et g "int -> int -> int" (d'où le nom "g", héhé malin), et il faut trouver un bout de code qui force "g" à être une fonction comme il faut :

Code :

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

1
2
3
let f x g =
   let retour_g = g 0 0 in
   if x = 0 && retour_g then 0 else 0

En écrivant "g 0 0", j'ai forcé g à admettre (au moins) deux paramètres de type "int", et le test sur "retour_g" force la valeur de retour à être de type "int" aussi (bien sûr la déclaration locale n'est pas nécessaire, tu peux écrire "&& g 0 0 = 0").

L'exercice devient plus intéressant, je trouve, avec des types polymoprhe. Tu as une idée de comment écrire une fonction de type 'a -> 'b -> ('c -> 'd) -> ('b -> 'a -> 'c) -> 'd ?

[alex_pi]

Je me permets de pas être d'accord avec un point des deux réponses précédentes. Moi si je suis un examinateur et que je demande une fonction de type int -> int -> int et une de type int -> (int -> int) et que l'élève ne me répond pas "c'est la même chose, je vous donne donc la même fonction", je considère qu'il n'a pas bien compris le parenthesage de la flèche..

[Cacophrene]

Salut !

Je me permets de pas être d'accord avec un point des deux réponses précédentes. Moi si je suis un examinateur et que je demande une fonction de type int -> int -> int et une de type int -> (int -> int) et que l'élève ne me répond pas "c'est la même chose, je vous donne donc la même fonction", je considère qu'il n'a pas bien compris le parenthesage de la flèche..

À moins que le cours n'ait jamais évoqué la curryfication et que l'enseignement ait été effectué en distinguant de manière très arbitraire les arguments d'une fonction et le résultat renvoyé (je ne sais pas si ce que je dis est clair). Évidemment passer à côté de ça est une énormité : on ne comprend plus vraiment l'utilité de la flèche, ni la puissance de l'approche fonctionnelle.

D'où : Déborah, dans ton cours, est-il fait mention de la notion de curryfication à un moment ou à un autre ?

Cordialement,
Cacophrène

[Jedai]

Je me permets de pas être d'accord avec un point des deux réponses précédentes. Moi si je suis un examinateur et que je demande une fonction de type int -> int -> int et une de type int -> (int -> int) et que l'élève ne me répond pas "c'est la même chose, je vous donne donc la même fonction", je considère qu'il n'a pas bien compris le parenthesage de la flèche..

Je suis complètement d'accord, si cette remarque n'est pas faite je ne mettrais pas le maximum des points même si toutes les fonctions fournies sont du bon type.

--
Jedaï

[gasche]

Non, moi je m'attends à des fonctions différentes justement (parce que les parenthèses permettent plus d'expressivité, c'est une manière de préciser au lecteur humain quelque chose), et d'ailleurs ça ne revient pas exactement au même parce que les fermetures seront placées diféremment (même si les types eux sont bien identiques).

Dans tous les cas, je trouve que c'est du détail, je comprends très bien que d'autres personnes aient un avis différent, par contre je trouverais abusif d'enlever des points à un examiné qui n'est pas du même avis.

[Jedai]

Dans tous les cas, je trouve que c'est du détail, je comprends très bien que d'autres personnes aient un avis différent, par contre je trouverais abusif d'enlever des points à un examiné qui n'est pas du même avis.

Ce n'est pas une question d'avis, même s'il mettait des fonctions différentes je serais content, à partir du moment où il fait la remarque que les types 1 et 3 sont en réalité identiques. Il me semble bien que la question est aussi là pour tester la compréhension du currying par l'examiné. (Dans le doute, et vu que la question ne comprend pas le "Avez-vous une remarque sur ces types ?" que je rajouterais si j'avais à la rédiger, je mettrais plutôt un bonus à ceux qui feront la remarque).
--
Jedaï

[ladeb]

Tout d'abord merci à tous pour vos réponses.

Je suis d'accord avec alex pi parce que mon prof m'a précisé que les parenthèses (quand elles sont situées à la fin) peuvent être omises.

Quant à la curryfication, mon prof de TD n'a pas vraiment assuré et nous n'avons fait que 2 exos sur le TD concerné. Vous voyez que j'ai du mal avec les "int", alors vous imaginez bien que quand on me demande d'écrire une fonction qui renvoie l'inférence 'a->'b->'c ou quelque chose comme ça, je suis un peu larguée!

En tout cas merci pour vos réponses, je vais encore me pencher là-dessus et si j'ai encore un souci, je vous redemanderai. De toutes façons, je pense qu'on se reverra dans le forum Java, vu que je suis perdue dans ce langage à cause des grèves de nos chers profs.

Déborah

[Jedai]

Vous voyez que j'ai du mal avec les "int", alors vous imaginez bien que quand on me demande d'écrire une fonction qui renvoie l'inférence 'a->'b->'c ou quelque chose comme ça, je suis un peu larguée!

Ca tombe bien que tu ais du mal à écrire cette fonction parce qu'en théorie tu ne peux pas... En effet ce type n'a pas d'habitant, tu ne peux pas prendre deux valeurs de deux types quelconques et renvoyer une valeur d'un type quelconque sans rapport avec les deux premiers. (En pratique tu peux utiliser "fail_with" pour obtenir ce type mais c'est acceptable vu que cette fonction ne terminera jamais vraiment (puisqu'elle s'achèvera en exception))

De même, on ne peut écrire 'a -> 'b, on peut écrire 'a -> 'a et la seule fonction (qui termine sans exception) de ce type est l'identité, de même la seule fonction de type 'a -> 'b -> 'a est (fun x y -> x), il n'y en a pas d'autres (fonctions pures) !

--
Jedaï

[alex_pi]

ATTENTION, ce qui va suivre peut embrouiller les débutants :

Je rappelle que quasiment personne ne code dans des langages normalisant (où toutes les fonctions terminent), et que donc, malheureusement, on peut se passer d'exception pour retourner quelque chose de n'importe quel type...

Code :

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

1
2
# let rec any_type () = any_type ();;
val any_type : unit -> 'a = <fun>

C'est bien ce qui fait qu'on peut difficilement les utiliser comme langage de preuve

[Jedai]

ATTENTION, ce qui va suivre peut embrouiller les débutants :

Je rappelle que quasiment personne ne code dans des langages normalisant (où toutes les fonctions terminent), et que donc, malheureusement, on peut se passer d'exception pour retourner quelque chose de n'importe quel type..

C'est vrai, c'est pour ça qu'en Haskell on a besoin d'introduire bottom dans la sémantique... Et de ce point de vue il y a toujours au moins un habitant à n'importe quel type : bottom, c'est à dire une valeur qui ne termine pas (ou qui "termine" avec une exception). Néanmoins on va dire qu'en général les types où bottom est le seul habitant ne sont pas très intéressants.

--
Jedaï

[gasche]

D'ailleurs quand on voit le traitement de bottom en Haskell, on se dit que les langages stricts dans le fond c'est pas mal, parce que les questions de lifting des types algébriques c'est quand même très laid.

[Jedai]

parce que les questions de lifting des types algébriques c'est quand même très laid.

A quoi fais-tu allusion exactement, je ne suis pas parfaitement sûr de ce que tu désignes par ces termes ?

--
Jedaï

[gasche]

Au fait que, par exemple, le nombre de représentants de (Either a b) n'est pas la somme des nombres de représentants de a et de b, ou que les types (t) et ((), t) et (t) ne sont pas isomorphes. C'est aussi pour ça qu'il y a "newtype" qui pourtant ne sert apparamment à rien, et que (let a = b in c) et (case b of a -> c) ne sont pas équivalents.

[Jedai]

Au fait que, par exemple, le nombre de représentants de (Either a b) n'est pas la somme des nombres de représentants de a et de b, ou que les types (t) et ((), t) et (t) ne sont pas isomorphes. C'est aussi pour ça qu'il y a "newtype" qui pourtant ne sert apparamment à rien, et que (let a = b in c) et (case b of a -> c) ne sont pas équivalents.

Je vois ce que tu veux dire, c'est effectivement laid, mais pas trop dérangeant en général
Par contre je conçois que ce soit difficile à comprendre pour un débutant, les différences sont subtiles et peuvent avoir des conséquences relativement importantes.

--
Jedaï