Salut, j'essaie de créer une fonction qui me permette de retirer tout les entiers négatifs d'une liste.

Pour cela j'introduit une premiere fonction :





qui calcule donc la longueur d'une liste.

Ensuite je créer ma fonction :



et la le probleme survient au moment de tester la fonction :

car elle fonctionne : int list list -> int list list

et le grand probleme c'est que normalement dans mes exemples a tester c'est du :

int list -> int list

donc .... quelqu'un voit il mon erreur ?

Merci encore







J'ai finalement trouver d'ou venait le probleme, j'avai penser a tout sauf a ca ^^, c'est en refesant l'erreur que je l'ai retrouvée :

EN fait, le 0 doit etre ecrit sans []

Voici donc le code propre :



Heuresement que j'ai perseverer avant d'aller me coucher. Incroyable comme des fois on trouve rapidement une solution sans le vouloir alors qu'en la cherchant fixement pendant longtemps on ne trouve rien ...

Rien n'est plus difficile a corriger que son propre code




Bon la je vais me coucher mais autant que ce sujet serve a quelquechose, j'ai pas vraiment eu trop le temps de chercher l'erreur (5 minutes seulement) mais bon :

J'essaie de calculer le nombre d'occurence d'un élément dans une liste :



Seulement ma fonction présence est définie de la facon suivante :


presence : 'a list * 'a -> bool = <fun>

donc x est considéré comme un element non identifié alors que quand j'introduit nb_occurence il paraitrait que mon x est devenue un element non identifié appartenant a une liste .... :

Toplevel input:
> else if (presence ( hd(s),x) = true) then (1 + nb_occurence ( tl(s),x ))
> ^
This expression has type 'a list,
but is used with type 'a.

Une syntaxe plus puissante

Tu connais le filtrage de motif ? C'est une manière beaucoup plus puissante d'utiliser les listes :


Si tu ne connais pas c'est dommage mais c'est pas vital dans ton cas.

Une fonction inutile

Déja ta fonction taille ne sert à rien, en effet elle n'est utilisée que pour tester le cas "taille s = 0", c'est à dire "s = []". Pourquoi ne pas mettre simplement "s = []" ?

L'inférence de type

Citation : Sateth

( hd (s) < [0] )

Voilà la partie qui fait croire à ocaml que tu manipules des types int list list :
hd (s) désigne le premier elelement de s, et tu le compares avec [0], qui est une liste contenant l'élément 0. Les éléments de s sont donc de type 'int list', s est donc de type 'int list list'.

Il faut écrire 'hd (s) < 0'.

Des exemples de codes plus simples

Avec les filtrages de motif :


Version Tail-recursive (aussi efficace qu'une boucle itérative) :



Sans les filtrages de motif (et sans tail-recursion) :

aie aie , tu adores le pattern matching pas moi

Sinon je n'ai pas vu le filtrage de motif, je viens de voir les listes

J'ai fini par retrouver l'erreur moi meême mais merci sinon jai poster u nouveau probleme si le coeur t'en dit

Merci encore beaucoup, je lirai attentivement ton texte a tete reposée demain. J'ai soif de connaissance.

Je ne trouve pas le nouveau problème...

Sinon, pour les pattern matching, je ne fais que suivre les recommandantions des développeurs Ocaml :
http://caml.inria.fr/resources/doc/guides/guidelines.fr.html

Citation : ocaml guidelines

Fonctions hd et tl

On n'utilisera pas les fonctions hd et tl mais un filtrage explicite de la liste argument.

Justification: C'est tout aussi bref et bien plus clair que l'usage de hd et tl qui doit nécessairement être protégé par un try... with... pour rattraper l'exception qui peut être déclenchée par ces fonctions.

Ok,
j'en parlerai a mon prof si il commance a nous apprendre le contraire de ce que recommande les devellopeurs

Sinon queue existe ? ou alors tu parles de tl (s) ?

Finalement a part ca et le fait que ton code est en pattern j'arrive a comprendre le programme

Dans le tail recursif par contre je ne vois pas pourquoi tu introduis une nouvelle fonction et je n'arrive pas a saisir le sens de :



Sinon je trouve excellent le coup de l'introduction de tete et suite, je pense que ca va pas mal m'aider.


MErci beaucoup

Mon code en général

filtrage de motif

Si tu as des problèmes avec le filtrage, je te conseille de lire ca :
http://www.pps.jussieu.fr/Livres/ora/DA-OCAML/book-ora016.html#toc14

C'est le cours "avancé" que j'ai lu, et même s'il n'est pas tout à fait simple (quand on a jamais fait de programmation fonctionnelle c'est un peu trash au début) il est bien expliqué et très complet.

queue

'queue' dans mon code n'est pas une fonction, mais une variable :
quand on fait un filtrage de motif sur une liste non vide de type :
| tete::queue -> .....
Cela déclare dans le code '....' la variable tete qui vaut (hd s) en gros et la variable queue qui vaut (tl s). En gros on dit au (O)caml :

Citation

Si la liste est de la forme "'tête' ajouté à la liste 'queue'", alors fait ceci cela

La fonction tail-récursive

principe

Le principe d'une fonction tail-récursive, c'est d'utiliser un 'accumulateur' pour stocker le résultat, et 'libérer' le résultat au moment où la fonction récursive, pour une raison d'optimisation expliquée ici :
http://fr.wikipedia.org/wiki/Récursion_terminale

Un exemple de fonction tail-récursive de base est la factorielle :
voici la version simple :



Voici la version simple avec filtrage de motif :



Et voici la version tail-récursive (je vais la faire sans pattern-matching) :

encapsulation

Le problème c'est que pour lancer la factorielle tail-récursive, il faut deux arguments : n et le résultat.
Au début, il faut que le résultat vaille 1.
Il faut donc au lieu d'écrire "fac n" écrire "fac n 1". Cependant si on n'a pas accès à la fonction factorielle (si c'est une librairie), il est impossible de comprendre l'utilité de ce deuxième arguement, qui doit toujours valoir 1 sinon le résultat est erroné.

L'idée est donc de masquer ce deuxième argument en encapsulant la fonction dans une deuxième fonction :



Ainsi, du point de vue de l'utilisateur, la fonction 'factorielle' se comporte tout à fait normalement : elle ne prend qu'un seul argument.

Le rev

Si j'ai mis "rev blabla" dans ma fonction, c'est parce que si tu réfléchis bien, tu verras que le premier élément de la liste de départ, puisqu'il est traité en premier, est envoyé le premier sur le dessus de la liste 'résultat'. Ainsi à la fin il sera le dernier élément de la liste résultat, qui est inversée. J'ai donc mis un 'rev' pour remettre les éléments dans l'ordre dans lequel ils ont été fourni par l'utilisateur.

Je saisis, j'ai pas encore visiter tes liens mais je voudrais savoir :

En quoi le tail recursif est il plus performant ? dans le cas de factorielle on ne fais pas plus ou moins de calculs ?

Donc en quoi c'est plus puissant ?

Désolé si je suis chiant

Citation : Sateth

Je saisis, j'ai pas encore visiter tes liens mais je voudrais savoir :

En quoi le tail recursif est il plus performant ? dans le cas de factorielle on ne fais pas plus ou moins de calculs ?

Donc en quoi c'est plus puissant ?

Désolé si je suis chiant

Bah en fait, avec la méthode non terminale, ça va se passer en deux temps.

Tout d'abord la "descente" de ta récursion qui fera un certain nombre d'appels de ta fonction.


Je reprend l'exemple de blue:



si on prend n = 5, la partie qu'on peut se représenter comme la "descente" est la période pendant laquelle la fonction ne peut pas donner de résultat.

donc quand on fait l'appel:
fac 5;;

on regarde n, il est différent de zéro, donc on fait n*fac (n-1), c'est à dire f(5)=5*fac(4). Seulement, on ne sait pas ce que faut fac(4).

On garde donc 5*fac(4), mais on calcule fac(4), ce qui nous donne puisque 4 est différent de 0, fac(4)=4*fac(3).

Encore une fois, on ne connais pas la valeur de fac(3). On calcule fac(3)

fac(3) = 3*fac(2).

toujours pareil, on calcule fac(2) = 2* fac(1), ce qui donne 5*4*3*2*fac(1)
On ne connais toujours pas fac(1), donc on a fac(1) = 1*fac(0).

C'est à partir de là (cas d'arrete de la récursion) que caml peut calculer le résultat, car il connait la valeur de fac(0), c'est 1

Du coup, caml sait maintenant que fac(5) = 5*4*3*2*1*1 (oui, on aurait du mettre le cas d'arrêt à 1 et pas 0... mais on va pas chipoter)

mais ce n'est qu'en remontant qu'il fera le calcul, c'est à dire il a son cas d'arret, et petit à petit il remonte dans les expressions pour trouver la valeur de fac(5).

En gros il se dit "j'ai fac(0), avec ça je peux trouver fac(1) car fac(1) = fac(0)*1", ensuite il a fac(1), et il fait la meme chose avec fac(2), encore et encore jusqu'a ce qu'il se dise "bon, j'ai fac(4), je peux enfin trouver fac(5) car je sais que fac(5) = 5*fac(4).

Et seulement à cet instant caml est capable de retourner le résultat. On peut considérer qu'il a parcouru deux fois la boucle.

Si par contre tu fais une fonction terminale, qui utilise par exemple un accumulateur comme à peu près celle de blue:



Occupons nous de la fonction récursive. Quand tu fais fac(5), caml va calculer n*resultat, au départ résultat vaut 1 (déclaration interne) donc il sera tout à fait capable de calculer directement 5*1 (=5 :p) , et il va rappeler facrec 4 5
puis multiplira 5 par 4, puis rapellera la fonction sous la forme facrec 3 20

Ensuite il mutiplie 3 par 20, ce qui fait soixante et rapelle la fonction facrec 2 60.

Ensuite il multiplie 2 par 60, ce qui fait cent vingt, et rapelle la fonction facrec 1 120.

n=1, cas d'arrêt, on retourne resultat, et resultat vaut 120. C'est factoriel de 5, c'est ce qu'on demandait. Il y aura eu 5 récursions, contre 10 pour l'autre (enfin, 12 puisque le cas d'arrêt est à zéro sur l'autre...)


Voila voila, ça n'a l'air de rien, mais la complexité d'un programme est à prendre en compte dès le début de des cours, même si ce ne sont que des notions de base, penser à optimiser un programme peut vous éviter pas mal de surprises dans l'avenir.

Sinon je trouve ça plutot étonnant qu'un prof vous apprennent les listes sur caml et que vous ne sachiez pas vraiment ce que vous faites.

Bonne journée.

La version tail-récursive est un plus, mais contrairement à iLUV je dirais que l'optimisation d'un programme c'est pas essentiel non plus :
il ne vaut mieux pas commencer à coder directement la fonction optimisée : fait la fonction simple, rapide à coder et qui marche, et si tu as du temps en plus tu peux toujours essayer d'optimiser.

Je me réfèrerais encore une fois à la "Ocaml programming Guidelines" :

Citation

Optimisation des programmes

Pseudo loi de l'optimisation:

Pas d'optimisation a priori.
Pas d'optimisation a posteriori non plus.

Programmer simple et clair avant tout. Ne commencer l'optimisation que lorsque le goulet d'étranglement du programme a été identifié (en général quelques routines). Alors l'optimisation consiste avant tout à changer la complexité de l'algorithme utilisé. Cela passe souvent par la redéfinition des structures de données manipulées et la réécriture complète de la partie du programme qui pose problème.

Justification:

Clarté et correction des programmes sont prioritaires. De plus, dans un programme conséquent, il est pratiquement impossible d'identifier a priori les parties du programme dont l'efficacité est primordiale.

Oui merci j'ai compris maintenant

Mais resultat on pourrait le remplacer par 1 ? ca changerai quoi ?

De plus la notation curifié ne donen rien de plus sinon rendre le programme moins lisible non ?

Merci en tout cas

Citation : Sateth

Mais resultat on pourrait le remplacer par 1 ? ca changerai quoi ?

où ça?

Citation

De plus la notation curifié ne donen rien de plus sinon rendre le programme moins lisible non ?

euh... flemme de tout relire, tete dans le cul jviens de me reveiller; où ça curryfication?

Pour la notation curyfiée, tu parles de laquelle ?

(si tu crois pouvoir nous faire taire en mettant ce topic comme 'résolu', tu fais une lourde erreur )

bluestorm est heureux qu'il y ai un nouvel ocamleur dans la salle.

Trop peu de monde s'interesse à CAML, et c'est pourtant tellement utile.

Donc comme t'es le seul à poser des question, bah poseeeeeeeeeeeeeeeeeeeeeee

Citation : Le prof

Caml ca sert a rien

Joli lapsus révelateur même si il s'est ratrapper apres

pour en revenir a nos moutons (mouton / ane/zozor ^^)

Je pensais a ce code :



(en ce qui concerne remplacer resultata par 1 et la notation curifiée)

Et bien, le code de la fonction est un peu plus long, mais pas tellement plus compliqué (surtout que quand on connait la tail-récursion on est habitué à cette structure
let fonction arg=
let auxiliaire =
...
in auxiliaire arg valeur_accu_par_defaut
;;)

Et en dehors de la fonction, tu appelles 'factorielle 34' sans te soucier de l'accumulateur (en fait tu fais pas la différence entre ca et l'implémentation moins efficace d'avant), donc ca te dérange pas.

Cependant, comme tu le soulignes ca complexifie un peu le code, donc il faut pas le faire si c'est pas une partie importante (au niveau du temps d'execution) du code.

Si t'as une boucle de 10 000 itérations qui apelle 239 fois la fonction à l'intérieur, ca peut devenir franchement intéressant.
Et c'est beaucoup plus simple et clair qu'une version itérative (avec une référence et une boucle for).

Je vois je vois, merci bien

(par contre je pense pas poser de questions avant une semaine minimum j'ai un peu trop de boulot pour commencer a coder un projet de fin d'anné maintenant ^^)

J'ai trouvé !!!!!!!!


Yes caml c'est trop bien, il a plus de secrets pour moi (jusqu'au prochain exo ...)


Alors voila la solution :

Le hd (s) va nous donner ..... du 'a !!!!

Voila ou était le problème !!

ET voila le nouveau code qui marche parfaitement !



Merci encore a bluestorm et iluv qui m'on beaucoup appris

Pourquoi tu écris encore tl(s) au lieu de tl s ?

Ton code marche peut-etre, mais à mon avis il fait beaucoup d'opérations inutiles. Tu pourrais nous montrer le code de présence (je crains le pire) ?

Tu connais les notions de complexité algorithmique ?

je viens de le mettre a ta facon

Compléxité ? bha il me faut du temps pour me mettre a cette nouvelle méthode et facon de penser


voila j'ai tout mis en curifié ce qui donne :