Caml : solution du TD 4

Une solution du TD 4 de Caml (v.16.1)

Exercice 1
let rec fact n = if n<1 then 1 else n*(fact (n-1));;

let rec gfact p = 

   if p==0; then 1

   else if (p<0 && (p mod 2)==0) then (gfact (-p))

   else if (p<0) then -(gfact (-p))

   else p*(gfact (p-1));;

La version ci-dessous de fibo a deux appels récursifs dont un seul, (fibo (n-2)), est terminal (càd est la dernière instruction de la fonction).

  let rec fibo n = 

     if n<=1 then 1 else (fibo (n-1)) + (fibo (n-2));;

Une version récursive terminale est plus compliquée :

    let rec fiboterm n f_1 f_0 =

       if n<0 then failwith "il faut n>=0"

       else if n=0 then f_0

       else if n=1 then f_1

       else (fiboterm (f_1+f_2) f_1);;

avec pour appel (exemple pour n=5) :
fiboterm 5 1 1;;
N.B. f_1=1 et f_0=1 correspondent aux deux premiers termes de la suite, n pourrait choisir d'autres valeurs pour généraliser la fonction Fibonacci.
Caml offre aussi la possibilité de donner des valeurs par défaut à des paramètres d'une fonction qui deviennent alors optionnels (hors du programme de L1-S1).
let fibog x = if (x<=0) then 1 else (fibo (int_of_float x));;
let rec u n x p = if n<=0 then x else p+.(u (n-1) x p);;
let rec v n x r = if n<=0 then x else r*.(v (n-1) x r);;

let rec nombrechiffres n = 

   if n<0 then (nombrechiffres (-n))

   else if n<10 then 1
   else 1+(nombrechiffres (n/10));;

let rec sommechiffres n = 

   if n<0 then (sommechiffres (-n))

   else if n<10 then n
   else (n mod 10)+(sommechiffres (n/10));;

let rec sommerecchiffres n = 

   if n<0 then (sommerecchiffres (-n))

   else if (n<10) then n 

   else sommerecchiffres (sommechiffres n);;

let puissance n p = if p<=0 

   then 1

   else  n*(puissance n (p-1));;

Exercice 2
let stringofchar c = String.make 1 c;;
N.B. il n'y a pas de fonction string_of_char prédéfinie en Caml.

let rec palindrome s =

  (String.length(s)<=0) ||

  ( (s.[0]==s.[String.length(s)-1]) && 
         palindrome (String.sub s 1 (String.length(s)-2)) );;

Exercice 3
En Caml, une fonction ne peut faire appel qu'à une fonction prédéfinie, il faut donc trouver une astuce :
(* fonctions définies pour n>=0 *)
let estpair n = true;;
let impair n = (n==1) || (estpair (n-1));;
let estpair n = (n==0) || (estimpair (n-1));;

Exercice 4

let rec listofstring s = 

   if s=="" then []

   else s.[0] :: (listofstring (String.sub s 1 (String.length(s)-1);;

let rec stringoflist t = 

   if t==[] then s

   else (stringofchar (List.hd t))^(stringoflist (List.tl t));;

let rec souschaine s d t =

   if (s=="" || t<=0 || d<0  || d>=String.length(s)) then ""

   else (stringofchar s.[d])^(souschaine s (d+1) (t-1));;

let rec contient s c =

   (not (s=="")) &&

   ( (s.[0]==c) || (contient (souschaine s 1 (String.length(s)-1) c) );;

N.B. Une évaluation logique s'arrête dès que l'expression peut être évaluée : (false && ...)→false, (true || ...)→true.

Exercice 5
2e élément de s : List.hd (List.tl s)
4e élément de s : List.hd (List.tl (List.tl (List.tl s)))
Supprimer les deux premiers : List.tl (List.tl s)
Accéder à la valeur 7 dans t : List.hd (List.tl (List.hd (List.tl t)))
Transformer t en [1;2;5;6;7] : (List.hd t)@(List.hd (List.tl t))
Transformer t en [[7;6];[5;2;1]] : (List.rev (List.hd (List.tl t)))::[ (List.rev (List.hd t)) ]

Exercice 6

let car s = match s with 

   | [] −> failwith "impossible d'extraire le premier élément"

   | t::q −> t;;

let cdr s = match s with

   | [] −> []

   | t::q −> q;;

let cons x s = x::s;;

let cadr s = match s with

   | []  −> failwith "impossible d'extraire le premier élément"

   | [a] −> failwith "impossible d'extraire le deuxieme élément"

   | t::u::q −> u;;

let estvide s = (s==[]);;

let rec longueur1 s = match s with

   [] −> 0

   t::q −> 1+ (longueur1 q);;

let rec longueur2 s = 

   if s==[] then 0 else 1+(longueur2 (cdr s));;

let rec memmetaille s t = match (s,t) with

   ([],[]) −> true

   ([],_)  −> false

   (_,[])  −> false;;
   _       −> memetaille (cdr s) (cdr t);;

let rec memmetailleIF s t = 

   if (s==[]) then (t==[])

   else memetailleIF (cdr s) (cdr t);;

let rec fusion s t =;

   if (s==[]) then t

   else (cons (car s) (fusion (cdr s) t));;

let rec inverser s = 

   if (s==[]) then []

   else (fusion (inverser (cdr s))  [(car s) []]);;

Exercice 7

let rec debut k s = 

   if (k<=0 || s==[]) ten []

   else (List.hd s)::(debut (k-1) (List.tl s));;

let rec fin k s =

   if (k==0 || s==[]) then []

   else if (k==(List.length s)) then s

   else (fin (k-1) (List.tl s));;

let rec sommeliste s =

   if (s==[]) then 0

   else (List.hd s)+(sommeliste (List.tl s));;

let rec produitliste s = 

   if (s==[]) then 1

   else (List.hd s)*.(sommeliste (List.tl s));;

let rec appartient x s =

   (s!=[]) && ( (x==(List.hd s)) || (appartient x (List.tl s)) );;

let rec oter x s = 

   if s==[] then []

   else if (x==(List.hd s)) then (List.tl s)

   else (List.hd s)::(oter x (list.tl s));;

let rec eliminer x s =  

   if s==[] then []

   else if (x==(List.hd s)) then (oter x (List.tl s))

   else (List.hd s)::(oter x (list.tl s));;

let rec expurger s = 

   if (s==[]) then []

   else (List.hd s)::(eliminer (List.hd s) (expurger (List.tl s)));;

Exercice 8

let rec somme f p = 

   if (p<0) then 0

   else f(p)+(somme f (p-1));;

Exercice 9

let rec sommecarre s = 

   if (s==[]) then 0

  ;; else ((List.hd s)*(List.hd s))+(sommecarre (List.tl s));;

let rec valeurmax s =

   if (s==[]) then min_int (* choix fait *)

   else (max (List.hd s) (valeurmax (List.tl s)));;

Toutes les valeurs de la liste seront supérieures ou égales à min_int qui est la constante donnant la valeur minimale possible pour un entier de type int.
N.B. Il serait possible de construire une fonction valeurmax qui n'utilise pas min_int et qui donne un failwith si la liste est vide.

Exercice 10

let rec syracuse n=

   il (n<1) then [1]

   else if ((n mod 2)==0) then n::(syracuse (n/2))

   else n::(syracuse (3*n+1));;

Si on donne un nombre négatif, cette fonction retourne [1].
Si la conjecture est fausse pour un nombre donné, le programme tourne indéfiniment, c'est-à-dire jusqu'à ce que la mémoire utilisable par Caml soit dépassée et que l'interpréteur Caml plante.
Si on oublie la condition de fin pour n=1, qui est impair, la fonction est rappelée avec les valeur successives n=3*1+1=4, n=4/2=2, n=2/2=1 ce qui boucle indéfiniment.