Types

Exercice 28

Définir un type expression_arithmetique permettant les entiers, les variables, les opérations unaires (oppose, racine carrée), binaires (addition, soustraction, multiplication et division). Et voici quelques exemples de constantes:

let e1 = Addition (Constante 2, Constante 2);;
e1 : expression_arithmetique = Addition (Constante 2, Constante 2)
let e2 = Multiplication (e1, (Racine (Variable "x")));;
e2 : expression_arithmetique =
 Multiplication (Addition (Constante 2, Constante 2), Racine (Variable "x"))
let e3 = Division (e2, Soustraction (e1, e2));;
e3 : expression_arithmetique =
 Division
  (Multiplication
    (Addition (Constante 2, Constante 2), Racine (Variable "x")),
   Soustraction
    (Addition (Constante 2, Constante 2),
     Multiplication
      (Addition (Constante 2, Constante 2), Racine (Variable "x"))))

Solution 28

Il est d'usage en Caml, de réserver la majuscule aux constructeurs et de laisser les types en minuscules.

type expression_arithmetique = 
    Constante      of int
  | Variable       of string
  | Addition       of expression_arithmetique * expression_arithmetique
  | Multiplication of expression_arithmetique * expression_arithmetique
  | Soustraction   of expression_arithmetique * expression_arithmetique
  | Division       of expression_arithmetique * expression_arithmetique
  | Oppose         of expression_arithmetique
  | Racine         of expression_arithmetique;;
Type expression_arithmetique defined.

Exercice 29

Calculer la hauteur d'une expression arithmétique.

Solution 29

Il est bon de respecter le même ordre entre la définition du type et les filtrages qui se fondent sur elle.

let rec hauteur_arbre = function
    Constante _             -> 1
  | Variable  _             -> 1
  | Addition (e1, e2)       -> 1 + max (hauteur_arbre e1) (hauteur_arbre e2)
  | Multiplication (e1, e2) -> 1 + max (hauteur_arbre e1) (hauteur_arbre e2)
  | Soustraction (e1, e2)   -> 1 + max (hauteur_arbre e1) (hauteur_arbre e2)
  | Division (e1, e2)       -> 1 + max (hauteur_arbre e1) (hauteur_arbre e2)
  | Oppose e                -> 1 + hauteur_arbre e
  | Racine e                -> 1 + hauteur_arbre e;;
hauteur_arbre : expression_arithmetique -> int = <fun>
hauteur_arbre (Variable "y");;
- : int = 1
hauteur_arbre e1;;
- : int = 2
hauteur_arbre e2;;
- : int = 3

Exercice 30

Écrire une fonction évaluant une expression arithmétique dépourvue de variables et de racine carrée.

Solution 30

let rec evaluer = function
    Constante n             -> n
  | Variable  _             -> failwith "Pas de variable!"
  | Addition (e1, e2)       -> (evaluer e1) + (evaluer e2)
  | Multiplication (e1, e2) -> (evaluer e1) * (evaluer e2)
  | Soustraction (e1, e2)   -> (evaluer e1) - (evaluer e2)
  | Division (e1, e2)       -> (evaluer e1) / (evaluer e2)
  | Oppose e                -> - (evaluer e)
  | Racine e                -> failwith "Pas de racine carree!";;
evaluer : expression_arithmetique -> int = <fun>

Exercice 31

Simplifier une expression arithmétique. On implantera, par exemple, 0+x=x, 0x=0, 1x=x, -(-x)=x ...

Solution 31

On peut ajouter encore et encore des cas.

let rec simplifier = function
    (Constante n) as c      -> c
  | (Variable s) as v       -> v
  | Addition (e1, e2)       -> 
     ( match simplifier e1, simplifier e2 with
         Constante v1, Constante v2 -> Constante (v1 + v2)
       | ee, Constante 0            -> ee
       | Constante 0, ee            -> ee
       | ee1, ee2                   -> Addition (ee1, ee2)
     )
  | Multiplication (e1, e2) -> 
     ( match simplifier e1, simplifier e2 with
         Constante v1, Constante v2 -> Constante (v1 * v2)
       | Constante 0, _             -> Constante 0
       | _, Constante 0             -> Constante 0
       | ee1, ee2                   -> Multiplication (ee1, ee2)
     )
  | Soustraction (e1, e2)   -> 
     ( match simplifier e1, simplifier e2 with
         Constante v1, Constante v2 -> Constante (v1-v2)
       | (Variable v1 as ee1), (Variable v2 as ee2)
                                    -> if v1 = v2 then Constante 0
                                       else Soustraction (ee1, ee2)
       | ee1, ee2                   -> Soustraction (ee1,  ee2)
     )
  | Division (e1, e2)       -> 
     ( match simplifier e1, simplifier e2 with
         Constante v1, Constante v2 -> Constante (v1/v2)
       | ee, Constante 1            -> ee
       | ee1, ee2                   -> Division (ee1, ee2)
     )
  | Oppose e                -> 
     ( match simplifier e with
         Constante v -> Constante (-v)
       | Oppose ee   -> ee
       | ee          -> ee
     )
  | Racine e                -> failwith "Pas de racine carree!";;
simplifier : expression_arithmetique -> expression_arithmetique = <fun>

Exercice 32

Écrire une fonction convertissant une expression arithmétique en une liste de chaînes de caractères le représentant sous forme préfixe. Par exemple,

lineariser_arbre e3;;
- : string list =
 ["/"; "*"; "+"; "constante"; "2"; "constante"; "2"; "sqrt"; "variable"; "x";
  "-"; "+"; "constante"; "2"; "constante"; "2"; "*"; "+"; "constante"; "2";
  "constante"; "2"; "sqrt"; "variable"; "x"]

Solution 32

let rec lineariser_arbre = function
    Constante c             -> ["constante"; string_of_int c]
  | Variable  v             -> ["variable"; v]
  | Addition (e1, e2)       -> ["+"] @ (lineariser_arbre e1) @ (lineariser_arbre e2)
  | Multiplication (e1, e2) -> ["*"] @ (lineariser_arbre e1) @ (lineariser_arbre e2)
  | Soustraction (e1, e2)   -> ["-"] @ (lineariser_arbre e1) @ (lineariser_arbre e2)
  | Division (e1, e2)       -> ["/"] @ (lineariser_arbre e1) @ (lineariser_arbre e2)
  | Oppose e                -> ["oppose"] @ (lineariser_arbre e)
  | Racine e                -> ["sqrt"] @ (lineariser_arbre e);;
lineariser_arbre : expression_arithmetique -> string list = <fun>

Exercice 33

Prendre le résultat d'une linéarisation et reconstruire l'arbre initial.

Solution 33

Ce qui suit s'inspire d'un style dit par continuations.

let elever_linearisation liste =
  let rec elever suite = function
    []                        -> failwith "Manque des termes"
  | "constante" :: c :: reste -> suite (Constante (int_of_string c)) reste
  | "variable" :: v :: reste  -> suite (Variable v) reste
  | "+" :: reste1           ->
        elever (fun e1 reste2 ->
                  elever (fun e2 reste3 ->
                           suite (Addition (e1, e2)) reste3 )
                         reste2 )
               reste1
  | "*" :: reste1           ->
        elever (fun e1 reste2 ->
                  elever (fun e2 reste3 ->
                           suite (Multiplication (e1, e2)) reste3 )
                         reste2 )
               reste1
  | "-" :: reste1           ->
        elever (fun e1 reste2 ->
                  elever (fun e2 reste3 ->
                           suite (Soustraction (e1, e2)) reste3 )
                         reste2 )
               reste1
  | "/" :: reste1           ->
        elever (fun e1 reste2 ->
                  elever (fun e2 reste3 ->
                           suite (Division (e1, e2)) reste3 )
                         reste2 )
               reste1
  | "oppose" :: reste       ->
        elever (fun e reste1 ->
                  suite (Oppose e) reste1 )
               reste
  | "sqrt" :: reste       ->
        elever (fun e reste1 ->
                  suite (Racine e) reste1 )
               reste
  | _ :: reste             -> failwith "Manque des termes"
in elever (fun e suite -> e) liste;;
elever_linearisation : string list -> expression_arithmetique = <fun>
elever_linearisation (lineariser_arbre (Oppose (Constante (3))));;
- : expression_arithmetique = Oppose (Constante 3)
e3 = elever_linearisation (lineariser_arbre e3);;
- : bool = true

Notez que comme l'on emploie des fonctions qui ne sont plus unaires, on a employé fun plutôt que function.