(*Exercice 1*)

(*Conformément à l'énoncé, pour tester*)
let f n = n + 1

(*Pour calculer la somme, il suffit d'une
  simple boucle.

  Ici, nous employons une boucle récursive :
  * si n < 0, la somme est 0
  * sinon, commencer par calculer la somme
  de 0 à (n - 1) puis ajouter (f n)

  Note : cet exercice avait été fait en TD.
*)
let rec somme f = function
  | n when n < 0 -> 0
  | n            -> (f n) + (somme f (n-1))

(*
  Variante récursive terminale : 

  acc contient la somme de (i+1) à n,
  initialisée à 0
*)
let somme2 f n =
  let rec aux acc = function
    | i when i < 0 -> acc
    | i            -> aux ((f i) + acc) (i - 1)
  in
    aux 0 n

(*
  En terme de nombre d'additions, ces deux fonctions ont 
  une complexité linéaire en n.
*)

(*
  Résultat des tests :

# somme f 5;;
- : int = 21
# somme2 f 5;;
- : int = 21

*)

(*Exercice 2*)

(*Conformément à l'énoncé, pour tester*)
let u n = n + 1;;
let v n = 2 * n;;

(*
  Il suffit de définir une fonction 
  f qui à tout i associe u(i)*v(n-i)
  puis de calculer la somme de f,
  à l'aide de l'exercice précédent.
*)
let convolution u v n =
  let f i = (u i) * (v (n - i))
  in
    somme2 f n

(*
  Ici encore, la complexité en nombre d'additions
  est linéaire en n.
*)

(*Exercice 3*)

(*
  Une simple fonction récursive :
  * si notre liste contient au moins deux
  éléments, c'est-à-dire si elle est de la 
  forme a::b::t, on garde a, on jette b et 
  on continue à enlever dans t
  * nous finirons bien par arriver à une liste
  contenant 0 éléments (si la liste est de
  longueur paire) ou 1 élément (dans le cas
  contraire), dans les deux cas, on garde la
  liste entière.

  Note : cet exercice est une version simplifiée
  d'un exercice obligatoire, qui avait été corrigé 
  en cours.
*)

(*
  Version récursive non terminale.
*)
let rec enlever = function
  | a::_::t -> a::(enlever t)
  | [a]     -> [a]  
  | []      -> []

(*
  Version un peu plus complexe, récursive 
  terminale.

  On parcourt la liste, en plaçant dans acc
  (initialement vide) les éléments à conserver. 
  Il reste à la fin la liste des éléments à
  conserver, qu'il ne reste plus qu'à inverser
  à l'aide de List.rev.
*)
let enlever2 l =
  let rec aux acc = function
    | a::_::t -> aux (a::acc) t
    | [a]     -> a::acc
    | []      -> acc
  in
    List.rev (aux [] l)


(*
  Exercice 4

  La fonction la plus intéressante de ce
  qui suit est un_melange :
  * une liste vide ou réduite à un élément
  est conservée telle quelle
  * confronté à une liste d'au moins deux
  éléments, on commence par tirer à pile
  ou face pour savoir si on échange ces
  deux éléments -- dans les deux cas,
  on continue à mélanger la liste ainsi
  obtenue.

  Le résultat n'est pas très mélangé
  mais ça répond à la question.

  La fonction un_melange n'est pas récursive
  terminale.
*)
let melanger l =
  let rec un_melange = function
    | []  -> []
    | [a] -> [a]
    | a::b::t when Random.bool () -> un_melange (b::a::t)
    | a::b::t -> a::(un_melange (b::t))
  in
  let rec repeter_melange l = function
    | 0 -> l
    | n -> repeter_melange (un_melange l) (n-1)
  in
    repeter_melange l (Random.int 5*(List.length l))

(*
  Ce qui suit est une version plus convaincante,
  inspirée de la manière de mélanger des cartes :
  - on coupe le jeu en deux au petit bonheur la
  chance
  - on replace les deux jeux en alternant les
  cartes de l'un et de l'autre aléatoirement
  - on recommence jusqu'à en avoir assez
*)

(*
  Pour fusionner deux tas de cartes en un tas acc
  - si l'un des deux tas est vide, on empile l'autre
  tas sur acc et on renvoie tout ça
  - sinon, on choisit un des deux tas au hasard, on 
    en prend la première carte, on l'ajoute à acc
    et on continue avec ce qui reste

  La fonction est récursive terminale, de complexité
  linéaire en (List.length g)+(List.length d)
*)
let fusionner_deux_tas_de_cartes g d = 
  let rec aux g d acc = 
    match (g,d) with
      | ([],_) -> d@acc
      | (_,[]) -> g@acc
      | (a::g', _) when Random.bool () -> 
	  aux g' d (a::acc)
      | (_, b::d')  -> 
	  aux g d' (b::acc)
  in
    aux g d []

(*
  Pour couper un jeu de cartes, tirer au hasard
  le numéro de la cartes où l'on coupe, mettre
  toutes les cartes avant ce numéro dans un tas
  acc et renvoyer ce tas acc et le tas des cartes
  restantes.

  Fonction récursive terminale de complexité linéaire
  en List.length l
*)
let couper_tas_de_cartes l =
  let rec aux i acc = function
    | []              -> (acc, [])
    | h::t when i > 0 -> aux (i - 1) (h::acc) t
    | l               -> (acc, l)
  in
    aux (Random.int (List.length l)) [] l


(*
  Enfin, on combine tout cela pour mélanger.

  Fonction récursive terminale, quadratique en 
  List.length l
  (on appelle jusqu'à List.length l fois
  chacune des deux fonctions précédentes).
*)
let melanger_comme_des_cartes l =
  let rec aux l = function
    | 0 -> l
    | i -> 
	let g,d = couper_tas_de_cartes l in
	  aux (fusionner_deux_tas_de_cartes g d)
	    (i - 1)
  in
    aux l (List.length l)


(*Exercice 5*)    

(*Pour retourner un tableau,
  la méthode est de
  - construire un nouveau tableau de même taille et
  de même type
  - recopier les éléments de l'ancien tableau vers
  le nouveau tableau à l'aide d'une boucle for ou
  d'une boucle récursive
  - renvoyer le nouveau tableau.
*)

(*
  Fonction non récursive, de complexité
  Array.length t en nombre d'accès à t
*)
let retourner t =
  let l = Array.length t in
  let t' = Array.create l t.(0) in
    for i = 0 to l - 1 do
      t'.(i) <- t.(l - i - 1)
    done;
    t'

(*Variante utilisant la bibliothèque OCaml :
  - transformer le tableau en liste
  - retourner la liste
  - transformer la liste en tableau*)
let retourner2 t = Array.of_list (List.rev (Array.to_list t))
(*Exercice 6*)

(*Pour vérifier si une liste est un palindrome,
  il suffit de vérifier si elle est égale à la
  liste une fois retournée.

  Pour retourner une liste, utiliser les fonctions
  vues en TD ou, plus simplement, List.rev
  
  Pour l'égalité, contrairement à Java, = suffit.
*)

let palindrome l =
  List.rev l = l

(*Exercice 7*)

(*Ici encore, au moins deux possibilités :
  - adapter la fonction a_l_americaine vue
    en TD, à condition de l'avoir comprise
    et de penser à réutiliser le module Exp
  - faire cela à coups de String.get et
    String.set. Les idées sont les mêmes,
    c'est juste plus simple.*)

(*
  Pour commencer, créer une chaîne t'
  à partir de la chaîne t, histoire de
  ne pas modifier t par accident.

  Ensuite, il suffit d'une boucle (ici, 
  une boucle récursive, on aurait pu utiliser
  un for) qui, pour chaque lettre ne commençant
  pas un mot met la lettre en minuscule. Ici,
  on se débrouille pour que debut soit true
  si la lettre en cours est au début d'un
  mot, false sinon. Pour déterminer si on
  est au début d'un mot, on applique la
  règle suivante :
  - la toute première première de t est au
  début d'un mot
  - si la lettre en cours suit une autre 
  lettre, elle n'est pas au début d'un mot
  - si la lettre en cours suit un caractère
  qui n'est pas une lettre, elle est bien
  au début d'un mot.

  Notez que cette version ne gère pas les 
  accents. D'un autre côté, comme on parle
  ici de titres anglo-saxons, ce n'est pas
  primordial.

  La fonction aux est récursive terminale,
  de complexité String.lenegth t
*)
let a_l_anglo_saxonne t =
  let t' = String.copy   t and
      len= String.length t in
  let rec aux i debut =
    if i >= len then
      t'
    else
      match String.get t i with
	| ('a'..'z' | 'A'..'Z' as c) -> 
	    if not debut then 
	      t'.[i] <- Char.lowercase c;
	      aux (i+1) false
	| _ ->
	    aux (i+1) true
  in
    aux 0 true

(*Exercice 8*)
(*
  Pour cet exercice, on pouvait argumenter aussi bien
  oui que non.

  Non : Il n'existe pas de fonction de type 'a -> 'b
  car une fonction, si jamais elle existait, devrait,
  pour tout type 'a et tout type 'b, accepter un argument
  de type 'a et renvoyer un argument de type 'b. En
  d'autres termes, cette fonction devrait être capable
  de renvoyer des éléments de n'importe quel type --
  y compris des types qui n'ont pas encore été inventés
  -- à partir de rien.

  Non bis : Si l'on considère ceci en logique, il
  existe une fonction de type 'a -> 'b si et seulement
  si il existe une preuve de "POUR TOUT f, POUR TOUT
  g, f IMPLIQUE g", ce qui est absurde.

  Oui : On peut construire de telles fonctions. Par
  exemple les fonctions impossible et impossible2
  qui suivent. Le point commun de toutes ces 
  fonctions est qu'elles ne peuvent pas s'exécuter
  correctement, sans causer d'erreur. Le 'b exprime
  ici que, si jamais ces fonctions arrivaient 
  jusqu'au bout, ce bout pourrait avoir n'importe
  quel type. Mais ceci ne peut pas arriver.
  Moralité : si vous avez une fonction dont le
  type ressemble à 'a -> 'b, c'est fort probablement
  que vous avez fait une erreur.

  Oui bis : il existe quelques fonctions de la
  bibliothèque standard OCaml qui sont de type
  'a -> 'b ou presque. La plus connue est Obj.magic, 
  qui demande à OCaml de tricher et de "faire 
  semblant" qu'une valeur de type 'a est en vérité 
  de type 'b, avec des résultats généralement 
  désastreux.

  Par exemple
  # let (a:int) = Obj.magic "5";;
  val a : int = -606216780
  # let (b:string) = Obj.magic a;;
  val b : string = "5"

  Cette fonction, assimilée par son auteur à une
  seringue usagée trouvée sur la voie publique,
  sert essentiellement à trois choses
  - transformer n'importe quoi en chaîne de
  caractères, de manière à sauvegarder le
  contenu de la mémoire dans un fichier
  - transformer une chaîne de caractères en
  n'importe quoi, de manière à recharger en
  mémoire le contenu d'un fichier
  - Coq -- dans lequel elle représente la
  preuve fausse universelle
*)

let impossible _ = failwith "vous avez essayé d'exécuter la fonction impossible"

let impossible2 _ = List.hd []