Programmation fonctionnelle

Partiel - sujet blanc

E. Lozes - novembre 2019

Durée : 2h

Exercice 1 - Triangle

Question 1.1 (2 points)

L'aire d'un triangle quelconque de côtés de longueurs $a$, $b$, $c$ est donnée par la formule $\sqrt{p(p-a)(p-b)(p-c)}$ où $p$ désigne le demi-périmètre du triangle. Définissez une fonction aire : float -> float -> float -> float telle que aire a b c est l'aire du triangle de côtés de longueur $a$, $b$, $c$. Vous ne devez pas calculer le demi-périmètre plusieurs fois.

Question 1.2 (2 points)

Définissez une fonction est_rectangle : float -> float -> float -> bool telle que est_rectangle a b c renvoie true si et seulement si le triangle de côtés $a$, $b$, $c$ est un triangle rectangle.

Exercice 2 - Plus grand élément d'une liste (4 points)

Définissez de trois façons différentes la fonction max_liste : 'a list -> 'a qui renvoie le plus grand élément d'une liste non vide quelconque (si la liste est vide, la fonction doit lever l'exception Invalid_argument "max_liste"

  1. Utilisez une définition récursive, et précisez en commentaire si elle est récursive terminale ou récursive enveloppée
  2. Utilisez une boucle for ou while
  3. Utilisez List.fold_left

On rappelle l'existence de la fonction max : 'a -> 'a -> 'a.

Exercice 3 - Décomposition en facteurs premiers

La décomposition en facteurs premiers (dfp) d'un entier $n\geq 1$ est la suite de ces facteurs premiers listés dans l'ordre croissant. Par exemple

  • la dfp de 140 est la suite 2,2,5,7
  • la dfp de 1 est la suite vide

Question 3.1 (2 points)

Définissez une fonction dfp_vers_entier : int list -> int qui a une décomposition en facteur premier associe l'entier correspondant. Par exemple, dfp_vers_entier [2;2;5;7] renvoie 140.

Question 3.2 (2 points)

Définissez la fonction inverse entier_vers_dfp : int -> int list. Vous pourrez utiliser une boucle for ou while et un style impératif, ou vous pourrez compléter la fonction ci-dessous

let entier_vers_dfp n = 
   let rec f n m = match (n, m) with
      | (1, _) -> []
      | (n, p) when n mod p = 0 -> ...
      | _ -> ....
   in f n ...

Question 3.3 (2 points)

Définissez la fonction dfp_produit : int list -> int list -> int list qui prend les dfp de deux nombres et qui calcule la dfp de leur produit. Par exemple, dfp [2;2;5] [2;3;7] renvoie [2;2;2;3;5;7].

Exercice 4 - Arbres binaires d'expression (3 points)

On rappelle le type des arbres binaires d'expressions vu en cours

type arbre = 
  | Feuille of feuille
  | Noeud of operateur * arbre * arbre
and feuille = 
  | Const of int
  | Var of string
and operateur = PLUS | SUB | MULT | DIV

Question 4.1

Définissez la fonction taille : arbre -> int qui calcule le nombre de noeuds internes d'un arbre (autrement dit le nombre d'opérations.

Question 4.2

Définissez la fonction hauteur : arbre -> int qui calcule la hauteur de l'arbre. On rappelle que la hauteur d'un arbre est longueur du plus long chemin de la racine à une feuille de l'arbre.

Question 4.3

Définissez la fonction variables : arbre -> string list qui calcule la liste des variables apparaissant sur les feuilles de l'arbre.

Exercice 5 - Somme d'un fichier (3 points)

Ecrivez une fonction somme_fichier : string -> int. L'entier somme_fichier nom_fichier renvoyé par la fonction est la somme des lignes de nom_fichier qui contiennent exactement un entier. Les autres lignes sont ignorées. Par exemple, si toto.txt est le fichier

30
il est 8 : 30
20
`

somme_fichier "toto.txt" renverra 50

Mémo

In [17]:
sqrt 2. +. 3. ** 2.
Out[17]:
- : float = 10.4142135623730958

List.fold_left (++) x0 [x1;...;xn] renvoie (...(x0++x1)++...)++xn.

In [4]:
List.fold_left (^) "" ["hello"; " "; "world"; "!"]
Out[4]:
- : string = "hello world!"
In [7]:
List.hd [1;2;3]
Out[7]:
- : int = 1
In [9]:
List.tl [1;2;3]
Out[9]:
- : int list = [2; 3]
In [11]:
let r = ref 0
Out[11]:
val r : int ref = {contents = 0}
In [18]:
while !r <> 10 do r := !r + 1; print_int !r done
Out[18]:
- : unit = ()
In [20]:
int_of_string "23"
Out[20]:
- : int = 23
In [21]:
int_of_string "23 : 30"

Exception: Failure "int_of_string".
Raised by primitive operation at unknown location
Called from file "toplevel/toploop.ml", line 208, characters 17-27
In [15]:
let premiere_ligne fichier = 
  let ic = open_in fichier in
  let res = input_line ic in
  close_in ic;
  res
Out[15]:
val premiere_ligne : string -> string = <fun>