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.

© 2016 – A. Sigayret