Salut à tous,
 
voilà l'énoncé de l'exo :
 
Ecrire une fonction decoupe qui parcourt une liste l et qui renvoie un triplet (l',e,l'') tq :
l=l'@(e::l'')
l' est triée en ordre croissant
e est plus petit que le dernier élément de l'
 
ex :
decoupe ([4;3;2;1]) renvoie : ([4],3,[2;1])
decoupe ([3;4;2;1]) renvoie : ([3;4],2,[1])
decoupe ([1;3;12;45;11]) renvoie : ([1;3;12;45],11,[])
decoupe ([1;2;3;4]) renvoie une exception: "pas de permutation plus grande"
decoupe ([1]) renvoie une exception : "pas de permutation plus grande"
 
J'ai programmé ça, mais l'affichage est incorrect, si quelqu'un pouvait m'aider, merci :-)
 
 
let rec decoupe liste=match liste with
 |[]->failwith "liste vide"
 |a:b::k)-> if a>b then a::b::k else [a]@(decoupe(b::k))
 |_->failwith "Pas de permutation plus grande";;
 
 
yoyoMC

sans le smiley c mieux :-) ... :
 
let rec decoupe liste=match liste with  
 |[]->failwith "liste vide"  
 |a:b::k)-> if a>b then a::b::k else [a]@(decoupe(b::k))  
 |_->failwith "Pas de permutation plus grande";;  

 
je te donne quelques pistes (je viens de le faire ) :

• selon l'énnoncé, tu dois retourner un tuple de la forme (list1,e,list2) , pour l'instant tu retournes une liste a::b::k .  
• Ca veut dire aussi que le [a]@(decoupe(b::k)) va être incorrecte. Il va falloir que tu récupères un tuple de la forme (list1,e,liste2) , que tu ajoutes a à list1 et que tu retourne le nouveau tuple
• pense au résultat de decoupe[1;2;2;2;2;3;4;0;5;4;8;7;4]

Une seule ligne est à modifier pour que ça marche,la 3°. Bon travail...

Oui merci, mais alors je dois utiliser l'opérateur de concaténation dans la première condition après le if a>b ?
 
Je ne vois pas très bien comment faire.  J'avais précédemment fait cette fonction aussi mais ça marche pas:
 
let rec decoupe liste=match liste with
 |[]->failwith "liste vide"
 |a:b::k)-> if a>b then ([a];[b];k) else ([a;b]@decoupe(k))
 |_->failwith "Pas de permutation plus grande";;
 
Merci
 
yoyoMC
 
 
 

 
En caml, un tuple c'est de la forme : (u,v,w), pas de ; . Et suivant l'ennoncé, tu n'as pas besoin de mettre b dans une liste.
 
Pour récupérer le tuple, tu fais :  
 ... let (l1,e,l2)=decoupe tesParametre in .... (* utilisation de l1,e,l2 *)

d'accord pour les : ",", je n'ai pas trop l'habitude de caml je débute, j'ai confondu.
 
Sinon, J'ai posé :
 
let rec decoupe liste=match liste with
 |[]->failwith "liste vide"
 |a::(b::k)-> let(l1,e,l2)=decoupe(?) in (if (a>e) then([a],e,k) else a@decoupe(k))
 |_->failwith "Pas de permutation plus grande";;
 
Je suis sur la bonne piste ou pas ? Maintenant je ne vois pas ce que je dois mettre dans decoupe... :-(

 
Quand a>e, tu n'a pas besoin de lancer récursivement découpe, tu renvois juste ([a], e, k) . D'ailleurs, j'ai découpé deux cas bien distinct :
   |a::b::k when a<b -> ([a],e,k)
   |a::b::k -> (* a>b *) let(l1,e,l2)=decoupe ? in ...
 
Reste plus qu'à trouver le ? et le ...
Pour le ?, tu viens de trouver deux nombres bien classés, il suffit de lancer decoupe sur le reste de la chaine
Pour le ..., tu viens de lancer decoupe qui t'a renvoyé (l1,e,l2), reste plus qu'à retourner un tuple construit à partir de l1,e,l2 et a qui soit la bonne solution.

Oui mais alors là ce que je comprends pas c'est quand a<b on renvoie ([a],e,k) ce qui voudrait dire qu'on a toujours qu'un seul élément pour le premier élément de notre tuplé ?
 
Autre question, je ne comprends pas comment on peut renvoyer un tuplé après un "in" ? Normalement ce qui est fait après le "in" se répercute avant dans le let.
 
Merci
 
yoyoMC

 
Oui, mais il faut dérouler l'algo pour bien comprendre. Par exemple compare [1;2;3;1;6;7] :

 
Non. Tout ce qui est fait après le in n'a aucune répercution sur ce qu'il y avant le let.
 
un exemple avec des tuples et un let :

C'est de la programmation fonctionnelle, donc beaucoup de récursif. C'est loin d'être évident au début. Il faut souffrir un peu mais on s'y fait très bien.

ok j'y vois bcp mieux niveau fonctionnement meme si je dois avouer que j'ai encore du mal pr finir l'exo :
 
let rec decoupe liste=match liste with
 |[]->failwith "liste vide"
 |a::b::k->when (a<b) then ([a],e,k) else let (l1,e,l2)=decoupe (k) in [a]@decoupe (k)
 |_>failwith "Pas de permutation plus grande";;
 
Ca y ressemble ?
 
Merci
 
 
yoyoMC

tiens c'est la rentrée

et non ! Ma rentrée est pour la fin du mois ! :-)
La seule chose vu que j'ai fait un peu de caml l'an dernier j'essayais de faire cet exo qu'on avait pas corrigé.

plutôt ça :
 
let rec decoupe liste=match liste with
 |[]->failwith "liste vide"
 |a::b::k->when (a<b) then ([a],e,k) else let (l1,e,l2)=decoupe (k) in l1@(e::l2)
 |_>failwith "Pas de permutation plus grande";;
 
Mais ça compile pas...

Quand tu compares a à b, n'oublie pas que la prochaine comparaison sera de b avec le premier élément de k. decoupe(k) est invalide.
 
[a]@decoupe(k) est une liste. Tu dois retourner un tuple    
 
 
PS : tu as un compilo caml sous la main ? Parceque logiquement ça ne passe pas à la compil.
 
 
edit : test      un smiley déconne  

"tu as un compilo caml sous la main ?"
 
Oui et c'est pour ça que je marquais au dessus que ça compilait pas ! lol
Bon j'essaie de corriger...

let rec decoupe liste=match liste with  
 |[]->failwith "liste vide"  
 |a::b::k->when (a<b) then ([a],e,k) else let (l1,e,l2)=decoupe (b::k) in l1@(e::l2)  
 |_>failwith "Pas de permutation plus grande";;  
 
"[a]@decoupe(k) est une liste. Tu dois retourner un tuple    "
Heu, là je ne vois pas où c'est dans mon algo ? Après le "in" ?

 
Oui, après le in (le  l1@(e::l2) ). Je sais pas où j'ai été cherché ça  
 
Edit: si j'ai trouvé, j'ai loupé ton dernier post

et on peut renvoyer un tuplet après un "in" ???

 
Bah bien sûr. La syntaxe "let toto in ...", c'est juste pour déclarer toto dans ce qui suit le in.

let rec découpe = fun (* FONCTION RECURSIVE OF COURSE *)
[] -> invalid_arg "pas de permutation plus grande"  (* SI A UN MOMENT ON OBTIENT LA LISTE VIDE ON RENVOIE L'ERREUR*)
|[x;y] when y>x -> [x],y,[] (* UN CAS SIMPLE A TRAITER *)
|(x::l) -> let (a,b,c) = découpe l in if x<= (hd a) then (x::a),b,c else [x], (hd a), (tl l) (* ET ICI ON AGIT RECURSIVEMENT DANS LES AUTRES CAS, AVEC UNE PSEUDO-SUBTILITE LORSQUE L'ON A UN CAS DE LA FORME [x;y] AVEC y<=x *);;

let rec découpe = fun  
[] -> invalid_arg "pas de permutation plus grande"  
|[x;y] when y>x -> [x],y,[]
|(x::l) -> let (a,b,c) = découpe l in if x<= (hd a) then (x::a),b,c else [x], (hd a), (tl l);;
 
 
(plus lisible comme ça désolé)

heu j'avoue ne pas comprendre là... la fonction me parait un peu bizarre, ça compile ?
Sinon, c'est quoi : hd et (tl l) ?

hd renvoie le premier élément d'une liste. tl renvoie la liste sans son premier élément. Oui, ça compile

Qu'est ce que tu ne comprends pas?

(hd a), c'est quoi hd ?
et : tl l, c'est quoi tl ?

cf ci-dessus!
Bonne nuit, MP moi si tu as des questions je te répondrai demain matin

"Bah bien sûr. La syntaxe "let toto in ...", c'est juste pour déclarer toto dans ce qui suit le in.  
"
Alors je ne vois pas dans l'exo ce qu'il faut mettre après le "in" : l'énoncé invite à renvoyer : l=l'@(e::l''), donc : l1@(e::l2), comment peux t-on renvoyer un tuplet ?

ok Volov, merci j'ai compris ta fct :-)

 
Tu compiles avec quoi ? Camllight ?
 
Sinon par rapport à l'énnoncé, c'est faux :  
- decoupe [1;2] doit retourner une erreur
- decoupe [2;1] ne doit pas retourner d'erreur
- tu lances decoupe l à chaque fois, or si l==[] tu déclenches l'invalid_arg. Par exemple sur decoupe [1;2;1];;
 

 
l=l'@(e::l'') définie l' , e et l''
Le résultat de la fonction, ce n'est pas l mais un triplet (l',e,l'')

Autant pour moi, j'ai parlé un peu vite. Il y avait d'ailleurs une faute de frappe dans mon premier programme (< au lieu de > ). Je compile sous Caml Light.
 
 
let rec découpe = fun  
|(y::x::l) when y>x -> [y],x,l
|(y::x::l) -> let (l1,e,l2) = découpe (x::l) in (y::l1,e,l2)
|_ -> invalid_arg "Pas de permutation plus grande";;  
 
 
est plus judicieux.
 
Je m'explique:
 
tant que les éléments sont dans l'ordre croissant au sens large, on continue (2ieme cas du pattern matching). Dès qu'il y a une rupture, on s'arrête (premier cas du pattern matching). Si on arrive à un moment à une liste à 1 ou 0 élément, c'est que la liste était croissante, donc on renvoie l'exception (EDIT: on pourrait se passer de la troisieme ligne, mais à ce moment là l'erreur ne serait pas "personnalisée" ).

 
   
C'est bizarre pour que ton exemple fonctionne avec Ocaml, il faut transformer le fun en function.
 
Moi j'avais ça (ce qui est exactement pareil)

 
 
Maintenant, si on veut faire ça très bien , il faudrait le passer en récursif terminal    

Oui ca fait partie des quelques différences marquantes entre Caml et Ocaml...
 
Ce n'est pas récursif terminal ça?
 
(enfin, j'imagine que récursif terminal signifie que tous les appels récursifs terminent, ce qui est le cas ici)

 
Récursif terminal, ça veut dire que la dernière instruction est l'appel récursif. Or ici, la dernière instruction est la construction d'un tuple. L'avantage du récursif terminal, c'est que caml peut optimiser l'algo et le dérécursiver.
Le moyen traditionnel d'y parvenir est d'ajouter un nouveau paramètre à la fonction qui fera office de pile.

Ok, je vois, du genre balancer en paramètre ce qu'il faudrait mettre devant le premier élément du triplet, du genre
découper y (x::l) au deuxième pattern matching, c'est ça?
 
le souci étant que cela oblige à faire ce que je voulais éviter (esthétiquement parlant ): une fonction externe non-récursive, du genre:
let découper l =
let rec découper...
in
....
 
 
Désolé je n'ai fait que de l'info en prépa mais cette année je m'y mets sérieusement

Oui c'est ça   .

"l=l'@(e::l'') définie l' , e et l''  
Le résultat de la fonction, ce n'est pas l mais un triplet (l',e,l'') "
 
Oui, je me comprends dans ce que je voulais dire... C'était une précision de l'énoncé pour présenter la récursivité sur l'exo ( genre de "déf inductive" )
 
Enfin j'ai bien compris
 
Merci