Discussion :

[Freedom57]

Bonjour , je cherche à coder une fonction qui renvoie le nombre d'occurence d'un caractere dans une chaine,voici mon code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
let rec nb_occ (car,ch)=let longueur=string_length(ch)
in if longueur=0 then 0
else if (nth_char(ch)longueur)=car then (1+nb_occ(car,sub_string(ch)0,longueur-1) else (nb_occ(car,sub_string(ch)0,longueur-1);;

Mais voici la réponse du terminal:



Voilà et je ne comprends pas pourquoi il ne veut pas prendre mon else.
Merci.

[gasche]

Tu as oublié une parenthèse dans le code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

(1+nb_occ(car,sub_string(ch)0,longueur-1)

[Freedom57]

Oui ,j'ai effectivement un probleme de parenthese.J'ai rectifié mais je me trouve maintenant avec un autre probleme:

Code caml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
#let rec nb_occ (car,ch)=let longueur=string_length(ch)
in if longueur=0 then 0
else if (nth_char(ch),longueur)=car then (1+nb_occ(car,(sub_string(ch)0,longueur-1)))else nb_occ(car,(sub_string(ch)0,longueur-1));;
Toplevel input:
>........nb_occ (car,ch)=let longueur=string_length(ch)
>in if longueur=0 then 0
>else if (nth_char(ch),longueur)=car then (1+nb_occ(car,(sub_string(ch)0,longueur-1)))else nb_occ(car,(sub_string(ch)0,longueur-1))..
This expression has type ((int -> char) * int) * string -> int,
but is used with type ((int -> char) * int) * ((int -> string) * int) -> int.

Du coup , je ne comprends ou j'ai fais mon erreur de typage.Si vous pouvez me guider...
Merci.

[gasche]

Quand on essaie d'aller au delà de l'erreur syntaxique, on doit comprendre le code et pour cela il est important qu'il soit lisible.

Tu devrais indenter correctement ton code. Indenter consiste à utiliser les espaces et les sauts de ligne pour mettre en valeur la structure logique du code : article wikipédia.

Voici une version indentée de ton code :

Code ocaml :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
let rec nb_occ (car,ch)=
  let longueur=string_length(ch) in
  if longueur=0 then 0
  else
    if (nth_char(ch),longueur)=car then
      (1+nb_occ(car,(sub_string(ch)0,longueur-1)))
    else
      nb_occ(car,(sub_string(ch)0,longueur-1));;

On respire déjà mieux.

(Après il y a plusieurs styles d'indentation, celui ci est peut-être un peu excessif mais c'est pour l'exemple.)


Ensuite, tu n'as visiblement pas compris comment utiliser les parenthèses en Caml. C'est une erreur courante chez les débutants.
Je t'invite à lire le document suivant, section 3.2 page 4, qui donne les bases du placement des parenthèses en Caml. C'est très simple mais il faut y donner cinq minutes d'attention si on ne veut pas se planter en continu.

Dans ton code le problème vient de "if (nth_char(ch),longueur)=car" : tu compares "car" à un couple constitué de "nth_char(ch)" (qu'est-ce que c'est que ça ?) et longueur. Ça n'a pas de sens.

Par ailleurs, il faut que tu te rappelles que les tableaux et les chaînes de taille N sont indexés de 0 à N-1. Essayer d'accéder à l'indice N d'une chaîne de taille N provoquera une erreur (une fois que tu auras corrigé les erreurs de typage).

Enfin, sub_string a un coût linéaire et est à bannir. Une récursion avec sub_string donne un algorithme quadratique. Dans tes appels récursifs, il ne faut jamais se rappeler sur une sous-chaîne, mais plutôt passer en paramètre l'indice du début de la sous-chaîne (ou l'indice de fin selon les cas), un simple entier.

[Freedom57]

Oui , effectivement le code était plutôt illisible.Je ferais mieux les prochain coups.

Dans ton code le problème vient de "if (nth_char(ch),longueur)=car" : tu compares "car" à un couple constitué de "nth_char(ch)" (qu'est-ce que c'est que ça ?) et longueur. Ça n'a pas de sens.

Mais nth_char est une fonction qui renvoie un cararctère.Alors en fait je compare un caractère à un caractère.Donc ça devrait avoir du sens , non?

Pour le reste , j'irais consulter les liens que tu m'as donné.

Merci.

[Freedom57]

Bon j'ai été sur ton site(très bon , d'ailleurs si tu peux me donner l'adresse de la page d'acceuil...) et j'ai lu particulierement le paragraphe sur les parentheses.Seulement j'ai pas du tout comprendre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
let rec nb_occ (car,ch)=
  let longueur=string_length(ch) in
  if longueur=0 then 0
  else
    if nth_char(ch longueur)=car then
      1+nb_occ(car,(sub_string(ch 0 longueur-1))
    else
      nb_occ(car,(sub_string(ch 0 longueur-1));;

Je ne mets plus de virgule pour séparer mes variables puisque il s'agit par ex pour nth_char d'un type:
string -> int -> char = <fun>
et non pas
(string * int)->char = <fun>
Est ce que j'ai déjà bien compris ça ou pas?

Ensuite le probleme de ce code est qu'il me rejette encore mon else.Je ne sais d'ailleurs pas si il s'agit du premier ou du deuxieme.

Merci pour ton aide.

[UnboundID]

Ensuite le probleme de ce code est qu'il me rejette encore mon else.Je ne sais d'ailleurs pas si il s'agit du premier ou du deuxieme.
Merci pour ton aide.

C'est le 2e else. Si tu regardes à la ligne d'avant, tu ouvres 3 parenthèses mais tu n'en refermes que 2. Il est donc normal que l'interpréteur ne s'attende pas à un else. Cependant rajouter une parenthèse ne résoudra pas le vrai problème.

Supposons que l'on ait une fonction f curryfiée ayant deux paramètres, alors les appels suivants sont équivalents :
f a b
(f a b)
f (a) (b)
par contre, f (a b) veut dire que b est le paramètre de la fonction a et le résultat de a b est le paramètre de f.

Supposons maintenant que l'on effectue l'appel sub_string ch 0 longueur-1. Comme l'application d'une fonction a une priorité supérieure à celle d'une opération arithmétique, c'est comme si on avait (sub_string ch 0 longueur)-1. Donc pour obtenir ce que tu désires, il faut appeler sub_string ch 0 (longueur-1).

Au final, on pourra écrire (avec nb_occ curryfiée):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
let rec nb_occ car ch =
  let longueur = string_length ch
  in if longueur = 0 then 0
     else
       let reste_ch = sub_string ch 0 (longueur-1)
       in if (nth_char ch (longueur-1)) = car
          then 1 + nb_occ car reste_ch
          else nb_occ car reste_ch;;

La remarque de bluestorm sur la complexité d'un algorithme utilisant sub_string est très pertinente. Cependant je suppose que tu es à la fac et il me semble que les étudiants qui commencent la programmation fonctionnelle n'ont souvent pas encore étudié la théorie de la complexité.

En intégrant la suggestion de bluestorm (utilisation d'un indice) on a :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
let nb_occ car ch =
  let rec aux i =
    if i = -1 then 0
    else if (nth_char ch i) = car
         then 1 + aux (i-1)
         else aux (i-1)
  in aux ((string_length ch)-1);;

Enfin si on veut la version récursive terminale :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
let nb_occ car ch =
  let rec aux i acc =
    if i = -1 then acc
    else if (nth_char ch i) = car
         then aux (i-1) (acc+1)
         else aux (i-1) acc
  in aux ((string_length ch)-1) 0;;

[Cacophrene]

Bonjour,

On peut aussi utiliser un itérateur tout simple pour éviter de s'embêter avec les indices... je ne connais pas l'équivalent caml light de ce code (s'il y en a un !). Et puis ici un fold aurait été plus sympa, méyapa... On doit donc faire un effet de bord dont je ne suis pas fan. Ça donne tout de même un code très simple.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
let nb_occ x str =
  let count = ref 0 in
  String.iter (fun y -> if x = y then incr count) str;
  !count

Cordialement,
Cacophrène

[Freedom57]

Bon , j'ai enfin réussi à faire tourner mon code.
Je prend note de ce principe de curyfication.

Cependant je suppose que tu es à la fac et il me semble que les étudiants qui commencent la programmation fonctionnelle n'ont souvent pas encore étudié la théorie de la complexité.

En effet , tu supposes bien.Et effectivement la théorie de la complexité , je ne connait pas.Y a du boulot en perspective...

Enfin voici mon code , peut être pas le plus performant , mais celui que j'ai compris et qui est le plus en "adéquation" avec l'enseignement que j'ai eu pour le moment...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
let rec nb_occ car ch=
	let longueur=string_length ch
		in if longueur=0 then 0
			else let reste_ch=sub_string ch 0 (longueur-1)
				in if nth_char ch (longueur-1)=car then 1+nb_occ car reste_ch 
						                else nb_occ car reste_ch;;

Et voilà l'exécution:

#nb_occ `o` "merci pour tout!";;
- : int = 2

Alors merci.

[gasche]

Pour formuler ma remarque sans aucune référence à de la complexité : sub_string *recopie* la sous-chaîne que tu lui demandes de te renvoyer. Demande la sous-chaîne de taille K demandera donc environ K opérations.

À chaque appel de ta fonction, tu recopies "longueur-1" éléments. Comme cette quantité (en fait longueur) diminue à chaque appel, jusqu'à atteindre 0, si la longueur de départ de ta chaîne est N tu as donc N-1 recopies, puis N-2 recopies (dans l'appel récursif imbriqué), puis N-3 recopies, etc. Au total tu as donc (N-1)+(N-2)+(N-3)+..+1 recopies, ce qui fait (N-1)*N/2 recopies, soit, en ordre de grandeur (à un facteur 2 et une constante près), N*N recopies.

C'est beaucoup, ça veut dire que pour une chaîne de taille 10^6 (un fichier d'un mégaoctet), ton algorithme va allouer des chaînes de taille de l'ordre de 10^12, 1000 gigaoctets !
Alors qu'il existe un algorithme tout aussi simple, dont des version ont été données dans ce topic, qui font exactement la même chose mais sans utiliser sub_string, donc aucune recopie, juste un parcours total de la chaîne (10^6 opérations sans utiliser de mémoire supplémentaire).

[drunkskater]

Mon message n'ajouteras pas grand chose puisque tout a été dit, mais j'ai fait voici deux codes de ta fonction occurences en Caml-Light :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
let occurences char string = 
  let rec aux position compteur =
    match position with
    | -1 -> compteur
    | n -> if string.[n] = char then aux (position - 1) (compteur + 1)
           else aux (position - 1) compteur
  in
  aux ((string_length string) - 1) 0
;;

Ce code est absolument identique à celui de UnboundID. La seule différence étant l'utilisation d'un match à la place d'un if. Ici, ça revient au même mais après c'est pratique d'utiliser des match surtout si on travaille sur des listes ou des couples (tu te retrouve typiquement avec, pour les listes, des trucs du genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
let fonction argument_1 ... argument_n =
  let rec fonction_auxiliaire liste accumulateur =
    match liste with
    | [] -> accumulateur
    | h::t -> if expression de h et des autres arguments then aux t f(accumulateur)
                else aux t accumulateur
  in
  aux argument_1 []
;;

)


Et voici un autre code, que je trouve plus naturel et qui correspond à la traduction en Caml Light du code de Cacophrène.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
let occurences char string =
  let compteur = ref 0 in
  for i=0 to ((string_length string) - 1) do
    if string.[i] = char then compteur := !compteur + 1
  done;
  !compteur
;;

Ne me demande pas pourquoi mais beaucoup de profs préfèrent le premier code... Je ne sais pas trop pourquoi, car autant il est vrai que dans beaucoup de cas l'écriture récursive est beaucoup plus belle, autant parfois (comme ici) je trouve que ça complique un peu les choses (dans le deuxième code on voit immédiatement ce que fait la fonction je trouve...). Peut-être qu'ils veulent s'assurer du fait qu'on maîtrise la récursivité terminale... Peut-être aussi que c'est plus simple à corriger (c'est ce que m'a confié un jour mon prof )

[gasche]

Une bonne raison d'encourager les débutants à écrire des fonctions récursives au lieu de boucles et références est le fait qu'en général, quand ils ont fait avant du Maple ou autres horreurs, ils sont très tentés de mettre des références partout, ce qui rend le code illisible, fragile, et les pousse à concevoir leurs programmes de la mauvaise façon.

Pour éviter ça, le plus simple est de leur demander de ne pas utiliser de références *du tout*, même si plus tard, avec la pratique, on apprend à en faire un usage raisonné (comme dans ce cas où une référence est effectivement une bonne solution).

[TropMDR]

Plusieurs commentaires en vrac:

@drunkskater: ton match à la place d'un if n'apporte rien, je trouve, en lisibilité. De plus, tu lies position à n, puis utilise n, ce qui fait qu'il faut au lecteur un effort supplémentaire pour comprendre le code.

Ensuite pour ce qui est de l'usage des fonctions pures et récursives : Je suis un grand fan de la récursivité ... sur les structures récursive (d'ailleurs en coq, c'est la seule qui est là de base ! c'est quelque part la plus "naturelle"). Or les chaines en caml (contrairement à haskell par exemple), ne sont pas des structures récursives. Ca me semble donc finalement peu naturel comme idiome. La définition "pour connaitre le nombre d'occurrence, je parcours la chaine et j'ajoute 1 à chaque fois que je rencontre le caractère" me semble finalement plus naturelle que "le nombre d'occurence de c à partir de l'indice n est 0 si n est la longueur de la liste ou est le nombre d'occurence de c à partir de l'indice (n +1), plus un si le caractère à la case n vaut c, plus zéro sinon".

Là où je suis en revanche d'accord, c'est qu'il faut inciter les débutants à ne pas utiliser de référence. Mais la solution me semble être de ne pas proposer d'exercice dont la solution la plus naturelle appelle à utiliser des références, plutôt que de trouver des solutions un peu tordues à de tels exercices.

Bref, moi j'aurais clairement codé ça avec une bonne vieille boucle for !

My 2c.

[drunkskater]

Pour éviter ça, le plus simple est de leur demander de ne pas utiliser de références *du tout*, même si plus tard, avec la pratique, on apprend à en faire un usage raisonné (comme dans ce cas où une référence est effectivement une bonne solution).

Ca me semble une raison valable

Pour l'histoire des "match" ou des "if", je suis tout à fait d'accord avec toi TropMDR mais l'année dernière on "m'obligeait" à utiliser des match partout... Mais j'avais un prof vraiment pas terrible

quand ils ont fait avant du Maple ou autres horreurs

J'ai connu ça. Et cette année je suis obligé de faire du Matlab !