Discussion :

[SpiceGuid]

Posez ici vos questions concernant le document en ligne L'approche qualité avec Objective-Caml.

Vous pouvez demander des compléments d'explication aussi bien sur les parties "cours" (les parties I, II et V) que sur les parties "application" (les parties III, IV et VI).

Quelques remarques utiles:

• utilisez le vocabulaire du tutoriel, en particulier un nom auquel est associé une valeur immuable est ou bien une variable (si la valeur ne peut être déterminée qu'à l'exécution) ou bien une constante (si la valeur peut être déterminée à la compilation)
• chaque chapitre est accessible par une balise html, de chapitre_1 à chapitre_47

Une liste des principales fonctionnalités du langage OCaml qui seront abordées dans les parties VII et VIII:

• le mot-clé when
• la définition de types exception
• les types algébriques

Une liste des autres principales fonctionnalités du langage OCaml (non couvertes par ce tutoriel):

• la notion d'êta-équivalence et les types '_a
• les mots-clé function, lazy, with, try...with
• les motifs pat1 | pat2
• l'égalité physique ==
• les fichiers d'interface *.mli
• les variants polymorphes
• les foncteurs
• la POO
• les labels

Pour les oublis, les fautes, les erreurs, les liens morts et autres modifications à apporter, veuillez me les soumettre par message privé, ceci afin de préserver au maximum cet espace au bénéfice des personnes en demande d'un soutien.

[james-mi]

Bonsoir,

je fais mes premiers pas en OCaml, à l'aide de ton tuto, et voici mes premières surprises :

Code :

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

1
2
3
4
# let rec factorial n = if n=0 then 1 else n * factorial (n - 1);;
val factorial : int -> int = <fun>
# factorial 5;;
- : int = 120

tout va bien pour l'instant

Code :

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

1
2
# factorial 25;;
- : int = -71303168

un problème avec les entiers je suppose ?

Code :

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

1
2
 factorial 50;;
- : int = 0

?? idem ?? comment fait-on pour éviter cela ?

et maintenant, le plus surprenant pour moi ... :

Code :

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

1
2
 factorial -1;;
This expression has type int -> int but is here used with type int

pourquoi le compilateur voit-il une erreur de type ?

maintenant je teste le mécanisme d'assertion, dont j'apprécie particulièrement le principe pour ce qu'il apporte en terme de sécurité :

Code :

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

1
2
3
let rec factorial n = 
assert(n >= 0);
if n=0 then 1 else n * factorial (n - 1);;

Code :

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

1
2
 factorial -1;;
This expression has type int -> int but is here used with type int

l'assert n'a pas fonctionné ?

Code :

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

1
2
# factorial (-1);;
Exception: Assert_failure ("", 44, 0).

quelle différence entre -1 et (-1) ?

bon, restons dnas la sécurité :

Code :

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

1
2
3
4
5
6
7
8
9
 let # let rec factorial n =
      match n with
      | 0 -> 1
      | m when m > 0 -> m * factorial (m - 1);;
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
1
(However, some guarded clause may match this value.)
val factorial : int -> int = <fun>

1 n'est pas "matched" ??
pourtant :

Code :

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

1
2
# factorial 1;;
- : int = 1

ça ne marche pas mieux avec la définition suivante, qui pourtant couvre tous les entiers :

Code :

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

1
2
3
4
5
6
7
# let rec factorial n =
    match n with
    | m when m < 0 -> failwith "non positive"
    | 0 -> 1
    | m when m > 0 -> m * factorial (m - 1) ;;
(* ou également à la dernière ligne :
    | _ -> n * factorial (n - 1) ;; (* qui fonctionne également *) *)

(j'ai toujours le même warning dont la signification m'échappe)

... Edit ... j'ai trouvé :

Code :

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

1
2
3
4
5
6
# let rec factorial n =
    match n with
    | m when m < 0 -> -999
    | 0 -> 1
    | _ -> n * factorial (n - 1) ;;        
val factorial : int -> int = <fun>

et cela marche très bien ...



Edit : si je suis hors sujet ici, dis-le moi, je posterai mes questions dans un autre thread

[SpiceGuid]

d'avoir accordé ta confiance à mon tutoriel.

Je vais supposer que tu as tout lu jusqu'au chapitre 14. Le filtrage inclus.

Code :

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

1
2
# factorial 25;;
- : int = -71303168

l'approche qualité en prend déjà un sérieux coup derrière les oreilles.
Scheme offre une vérification du dépassement de capacité des int mais pas OCaml (pour des raisons de performance).

Code :

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

1
2
# factorial 50;;
- : int = 0

Idem.

Code :

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

1
2
# factorial -1;;
This expression has type int -> int but is here used with type int

C'est une soustraction, en effet c'est le même code que factorial - 1.
L'inférence de type déduit donc que factorial est de type int.
Or tu viens de définir factorial comme étant de type int -> int.
Manifestement les deux types sont incompatibles.

Code :

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

1
2
3
4
5
6
7
8
9
# let rec factorial n =
      match n with
      | 0 -> 1
      | m when m > 0 -> m * factorial (m - 1);;
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
1
(However, some guarded clause may match this value.)
val factorial : int -> int = <fun>

Mon chapitre 14. Le filtrage n'aborde pas la clause when, je vais toutefois te répondre:

• ton filtrage n'est pas exhaustif, (-1) n'est filtré par aucune de tes deux clauses
• OCaml pense que 1 pourrait ne pas être filtré car, à la compilation, il voit toute garde when comme une garde when false

La garde when ne peut pas servir à préciser le domaine de définition.
La bonne version est :

Code :

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

1
2
3
4
5
6
# let rec factorial n =
    assert(n >= 0);
    match n with
    | 0 -> 1
    | m -> m * factorial (m - 1);;
val factorial : int -> int = <fun>

Si malgré tout tu souhaites utiliser des gardes voici la bonne façon :

Code :

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

1
2
3
4
5
6
# let rec factorial n =
    match n with
    | m when m < 0 -> assert false
    | m when m > 0 -> m * factorial (m - 1)
    | _ -> 1;;
val factorial : int -> int = <fun>

[gasche]

Code :

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

1
2
3
4
let rec fac = function
| neg when neg < 0 -> invalid_arg "fac"
| 0 -> 1
| n -> n * fac (n - 1)

Je préfère ce code parce qu'il utilise une seule garde, et que le cas "0 -> 1" est plus explicite que le "_ -> 1" du dernier code proposé. A-t-il un inconvénient ?

[SpiceGuid]

Aucun inconvénient.

Simplement assert est plus général et cet usage du when ne marchera pas avec les fonctions de la partie III.

[james-mi]

d'avoir accordé ta confiance à mon tutoriel.

ça alors, c'est toi qui a fait tout le travail, et en plus tu me rees !!!

Je vais supposer que tu as tout lu jusqu'au chapitre 14. Le filtrage inclus.

lu, oui , mais assimilé ... c'est encore à venir?

Code :

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

1
2
# factorial 25;;
- : int = -71303168

l'approche qualité en prend déjà un sérieux coup derrière les oreilles.

bon alors parlons-en, justement, parce que moi la qualité cela m'intéresse au plus haut point ... je propose de reprendre ce sujet sur un autre thread pour ne pas polluer celui-ci : rendez-vous là: http://www.developpez.net/forums/sho...32#post3072732

et à plus tard ici pour de nouvelles aventures ...

[SpiceGuid]

On revient sur le module du chapitre 57 qui implémente les arbres binaires 'a tree avec éléments aux noeuds, de taille size et de profondeur depth.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
module BinaryTree = struct 
  type 'a tree =
    | Leaf
    | Node of ('a tree) * 'a * ('a tree)
  let fold f init t =
    let rec loop t = 
      match t with
      | Leaf -> init
      | Node(l,a,r) -> f (loop l) a (loop r)
    in loop t
  let size t  = fold (fun l a r -> l + r + 1) 0 t
  let depth t = fold (fun l a r -> max l r + 1) 0 t
  let mem x t = fold (fun l a r -> l or x=a or r) false t
end;;

La fonction mem teste l'appartenance de x à un arbre binaire t.

Un arbre binaire ordonné est un arbre binaire qui vérifie les deux propriétés suivantes:

• l'élément porté par un fils gauche est strictement plus petit que l'élément porté par son parent
• l'élément porté par un fils droit est strictement plus grand que l'élément porté par son parent

Question 1:

La fonction mem x t effectue la recherche dans un arbre binaire (ordonné ou non).
Codez une fonction insert x t qui effectue l'ajout d'un élément x dans un arbre binaire ordonné t.


Question 2:

Recodez la fonction insert x t, mais cette fois-ci sans utiliser la récursion, à la place utilisez le catamorphisme fold.

EDIT: je m'excuse pour ceux qui ont cherché à coder le prédicat ordered qui dit si un arbre binaire est ordonné, cette question est probablement trop difficile, j'avais édité ce message et je croyais l'avoir retirée à temps mais apparemment ça n'était pas le cas.

[gasche]

Détail stylistique :

Code :

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

let size t  = fold (fun l a r -> l + r + 1) 0 t

Pour avoir un code un peu plus significatif, et éviter le warning "unused variable ...", tu pourrais faire :

Code :

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

let size t  = fold (fun l _ r -> l + r + 1) 0 t

[InOCamlWeTrust]

Tout à fait d'accord : un bon code OCaml ne doit jamais faire apparaître des identificateurs non utilisés. D'ailleurs, je me rends de plus en plus compte que l'on n'utilise, en réalité, que très peu d'entre eux.

[james-mi]

Au fait, Spice, tu pourrais mettre ton tuo à disposition sous forme pdf ? ça simplifierai grandement sa consultation ...

[SpiceGuid]

Plus je lis le Initiation à la programmation fonctionnelle de Jean-Christophe Filliâtre plus je trouve que mon texte est inutilement pédant.
En plus il couvre davantage du langage que le mien et il est en pdf et en ps.

Vraiment je le recommande.

Par contre mes exemples sont un petit peu plus développés, j'accorde plus de place au style à adopter, au point sans doute que j'aurais du me contenter de commenter du code.

Il est un peu tard pour songer à une version pdf, c'est une attente qu'il fallait prendre en compte à la rédaction, par contre je peux fournir une version html hors-ligne.

[james-mi]

En tout cas il m'a été utile, et je pense qu'il peut me l'être encore...

Beaucoup plus complet à mon avis que Filiatre.

je suis preneur d'une version html off-line

[SpiceGuid]

Nouveau format pour le cours, maintenant disponible en pdf.

• pas de d'index
• pas de parties application (III,IV,VI)

[james-mi]

merci !

[SpiceGuid]

Des petites retouches, surtout dans la partie II, la plupart inspirées par les remarques avisées d'alex_pi.

Le pdf a aussi été mis à jour pour correspondre à la version en ligne.

[gasche]

Désolé pour un détail sans intérêt, mais il y a des problèmes de rendu sur la version web. Par exemple sur cette page http://damien-guichard.developpez.co...caml_0002.html , on trouve pas mal d'occurences de "&arr", "&alpha", etc.

[SpiceGuid]

Le seul navigateur avec lequel j'ai un rendu "&alpha &rarr &beta" au lieu de "α → β" c'est IE 6.0. D'un autre côté je suis absolument nullissime en encodage web.

Code :

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

  <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />

Où est mon erreur, ça n'est pas le bon charset ou c'est autre chose ?

À chaque fois que je relis mon cours je trouve qqch chose qui a changé (en mal) et je dois corriger, cette fois c'est Wikipédia qui n'assure pas la continuité de ses liens images

[gasche]

Je viens de tester sous Firefox et Google Chrome, et les deux affichent pareil. Ça me semble assez normal, il y a par exemple "<I>..</I> &rarr <I>...</I>" dans le source, et à ma connaissance &rarr n'est pas un format d'entité HTML.

[SpiceGuid]

à ma connaissance &rarr n'est pas un format d'entité HTML

symbols, html 4.0

Mon erreur venait de l'omission du point-virgule à la fin des symboles, j'avais cru comprendre qu'il était facultatif (ça s'affichait bien sur plein de navigateurs) mais finalement on dirait que non.
corrigé.