Discussion :

[Shekyl]

Bonjour,

Est-ce que quelqu'un peut m'expliquer ce qu'est un itérateur sur un type quelconque svp?
Par exemple, si j'ai ce type là:

Code :

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

1
2
3
4
5
 
type exp= 
   | Const of int
   | Add of exp*exp
   | Sub of exp*exp;;

Quel sera le type de l'itérateur? Il doit retourner quoi et comment on l'utilise svp?

Merci d'avance

[SpiceGuid]

Le mot itérateur possède une certaine connotation de linéarité comme List.fold_right ou comme un chemin (une liste qui mène de la racine à un nœud) dans un arbre binaire.

Quand c'est une notion plus généralisée, il n'y a pas de vocabulaire standard mais en général on utilise 1 parmi ces 3 mots :

1. Les haskelleurs préfèrent parler de fold généralisé.
2. Les catégoriciens préfèrent parler de catamorphisme ou de paramorphisme.
3. Les logiciens préfèrent parler d'éliminateur.

Et personnellement je préfère parler de récurseur :

• D'abord parce que je suis un programmeur, je ne veux pas être étiqueté comme haskelleur/catégoricien/logicien.
• Ensuite parce que le but de la chose c'est d'encapsuler la récursion : grâce au récurseur le code est plus concis car il n'y a pas de récursion explicite.

Malheureusement OCaml ne génère pas le récurseur à ta place, bien que cette opération soit tout à fait automatisable.

Ton type expr :

Code :

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

1
2
3
4
type expr = 
   | Const of int
   | Add of expr * expr
   | Sub of expr * expr

Tu dois ensuite réifier le filtrage sur expr, c'est-à-dire en faire un objet :

Code :

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

1
2
3
4
5
6
type 'a expr_case = 
   <
   const: int -> 'a;
   add: 'a -> 'a -> 'a;
   sub: 'a -> 'a -> 'a;
   >

Puis tu dois coder le récurseur qui contient tous les appels récursifs :

Code :

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

1
2
3
4
let rec expr_rec (c:'a expr_case) = function
   | Const n  -> c#const n
   | Add(a,b) -> c#add (expr_rec c a) (expr_rec c b) 
   | Sub(a,b) -> c#sub (expr_rec c a) (expr_rec c b)

Enfin tu utilises ton récurseur de cette façon :

Code :

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

1
2
3
4
5
6
7
8
9
let eval =
   expr_rec
   (
   object
      method const n = n
      method add a b = a + b
      method sub a b = a - b
   end
   )

Ça a l'air compliqué et inutile.
Cependant ça se justifie très bien si tu veux coder d'autres fonctions sur le type expr.

Par exemple pour faire la somme de toutes les feuilles const :

Code :

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

1
2
3
4
5
6
7
8
9
let sum =
   expr_rec
   (
   object
      method const n = n
      method add a b = a + b
      method sub a b = a + b
   end
   )

Tu veux compter le nombre de nœuds add :

Code :

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

1
2
3
4
5
6
7
8
9
let adds =
   expr_rec
   (
   object
      method const n = 0
      method add a b = a + 1 + b
      method sub a b = a + b
   end
   )

Tu n'es plus jamais embêté par la récursion !

Remarque 1 : Pour d'obscures raisons syntaxiques (que j'ignore) les parenthèses autour de object...end sont obligatoires.
Remarque 2 : Il existe des langages (plus ou moins) ésotériques qui sont capables de générer le récurseur automatiquement à partir de la définition du type.

[Shekyl]

Merci beaucoup pour ce bel exemple^^

J'ai compris comment faire, mais une derniere question:

Vaut-il mieux faire comme ce que tu as fais, ou faire comme cela:

Code :

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

1
2
3
type equ = | Const of int
           | Add of equ*equ
           | Sub of equ*equ;;

Code :

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

1
2
3
4
5
  let recEqu = fun fConst ->  fun  fAdd -> fun fSub -> 
                 let  rec frec = function | Const(x) -> fConst x
                                          | Add(x,y) -> fAdd (frec x) (frec y)
                                          | Sub(x,y) -> fSub (frec x) (frec y)
                in frec;;

Et pour mettre sous forme de string:

Code :

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

   let    recEquAfficher  = recEqu (fun x -> string _of_int x) (fun x -> fun  y -> "("^x^"+"^y ^")") (fun  x -> fun y -> "  ("^x^"-"^y^")");;

[SpiceGuid]

Ça ne fait pas de différence calculatoire, c'est une question de goût/lisibilité/performance.
Mon style est sans doute plus verbeux sur un exemple simpliste.
Cependant il peut devenir plus lisible sur des données plus riches.

Voici un autre exemple un peu plus étoffé pour comparer :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
type r_to_r =
   | X
   | Cst of float
   | Neg of r_to_r
   | Add of r_to_r * r_to_r
   | Mul of r_to_r * r_to_r
   | Sin of r_to_r 
   | Cos of r_to_r
   | Exp of r_to_r
   
let rec recu c = function
   | X -> c#x
   | Cst n -> c#cst
   | Neg u -> c#neg (recu c u)
   | Add (u,v) -> c#add (recu c u) (recu c v)
   | Mul (u,v) -> c#mul u (recu c u ) v (recu c v)
   | Sin u -> c#sin u (recu c u)
   | Cos u -> c#cos u (recu c u)
   | Exp u -> c#exp u (recu c u)

let deriv =  
   recu (      
      object 
         method x = Cst 1.
         method cst = Cst 0.
         method neg du = Neg du
         method add du dv = Add (du,dv)
         method mul u du v dv = Add (Mul (du,v), Mul (u,dv))
         method sin u du = Mul (du, Cos u)
         method cos u du = Neg (Mul (du, Sin u))
         method exp u du = Mul (du, Exp u)
      end )

[Shekyl]

D'accord, merci beaucoup pour ton aide.