Discussion :

[guipe]

Bonjour,toujours dans ma découverte de Caml, je dois créer une fonction qui vérifie si une liste est triée.

Voici ce que j'ai fait :

Code :

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

1
2
3
4
5
6
7
8
9
 
 
let l=[3;4;5;6] ;;
let p= (fun x y -> x < y)
 
let rec triee l p =
				  if l = [] then true
				  else if ((p (hd l) (hd (tl l))) = false ) then false
				  else (true & (triee (tl l) p ));;

Ma dernière ligne est fausse,je ne sais pas comment l'écrire.

J'explique mon algo. Si ma liste est nulle alors ma liste est triée je renvoie true. Si le premier élément de ma liste et le second appliqué à ma fonction p donne faux(le premier élément est supérieur au second) alors je renvoie false.
C'est ce qui vient ensuite que j'ai du mal à définir.
Ce que je voudrais faire c'est renvoyer true "et" triée "reste de la liste".
Je pensais mon algo bon mais ça ne fonctionne pas.

Merci de votre aide !

[Steki-kun]

C'est pas vraiment ta dernière ligne qui est fausse c'est plutôt la deuxième, même si le tout est écrit de manière assez bizarre. Ta deuxième ligne part du principe qu'il y a au moins 2 éléments dans la liste, tu ne traites nulle part le cas d'une liste singleton.

Plusieurs remarques en vrac:
- on n'écrit pas "if t = false then false else u", mais plutôt t && u, non ?
- d'ailleurs, on n'écrit pas en général des tests du genre "if e = true then" ou "if e = false then", mais plutôt "if e" ou "if not e"
- & est obsolète, il faut utiliser &&, et de toute façon "true && e" c'est équivalent à e dans c'est bizarre d'écrire ta dernière ligne comme tu l'as fait
- évite de faire des if en cascade et d'utiliser hd et tl pour analyser la liste passée en argument, Caml met à ta disposition quelque chose de + élégant et de moins bug-prone, le pattern matching.

Voilà le squelette d'une définition avec pattern matching, je te laisse compléter les blancs:

Code :

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

1
2
3
4
5
 
let rec triee p = function
  | [] -> ...
  | [a] -> ...
  | a::b::q -> ...

On peut encore l'écrire un peu mieux que ça mais déjà elle aura l'air beaucoup + claire comme ça ta fonction

[gasche]

Par ailleurs (après la réponse de Steki-kun qui est vraiment très bien, on se limite aux petits détails), pour l'indentation du code ce n'est toujours pas ça : indenter énormément n'aide pas à la lisibilité, puisqu'on se met à dépasser en largeur dans la fenêtre qui affiche le code.

[guipe]

Code :

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

1
2
3
4
let rec triee l p =
		  fun [] -> true |
		  [h] -> true |
		  (h::t) -> triee t p ;;

Ca ne fonctionne toujours pas ...

[gasche]

Normal, tu as oublié d'utiliser 'p'.

Tu devrais essayer de réutiliser le squelette de code donné par Steki-kun, il est là pour t'aider.

[guipe]

Code :

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

1
2
3
4
let rec triee  =
		 fun p [] -> true |
		 p [h] -> true |
		 p l -> ((p (hd l) (hd(tl l))) && (triee p tl(l)) );;

Je pensais que c'était bon là mais non !

Pourtant c'est bien ça ma fonction prend une fonction p et une liste en argument.Bref j'aimerai vraiment comprendre mes erreurs ici. Merci du temps que vous me consacrez !

[LLB]

Quel est le problème ? Erreur du compilateur ? Erreur à l'exécution ?
Dans le premier cas, lis le message, il te dira ce qui ne va pas. Sinon, essaie de comprendre ce qu'il se passe, en testant plusieurs entrées.

Prends le temps d'expliquer clairement le problème ("ça ne marche pas" n'est pas suffisant). Dans beaucoup de cas, expliquer en détails ce qui ne va pas t'aidera à résoudre ton souci. Dans les autres cas, ça fera perdre moins de temps à ceux qui veulent t'aider (on n'a pas forcément Caml sous la main).

[drunkskater]

Salut,

Moi aussi je suis débutant donc ce que je vais raconter est à confirmer, mais :

• Dans ton dernier code, ta fonction n'a pas d'argument. Ceux-ci devraient se trouver avant le signe "=". Si j'ai bien compris, tu veux une fonction qui regarde si une liste l est triée selon un ordre p, donc la définition de ta fonction va forcément commencer par " let rec triee l p = ... "
  
• Essaie de suivre le "squelette" donné par Steki-kun ainsi que ses conseils. Néanmoins j'avoue que je ne comprend pas trop son code puisqu'il ne prend que p comme argument (p serait donc la liste, mais alors il n'y aurait pas de fonction de comparaison ??).
  
• Si jamais tu n'est pas fan de la syntaxe avec "function" pour le pattern-matching (comme c'est mon cas, mais j'ai surement tort et ça vient simplement du fait qu'on ne m'a jamais expliqué comment ça marchait), tu peux utiliser un "match". L'expression :
  

  Code :

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

  1
  2
  3
  4
  5
  match u with 
  | motif 1 -> expression 1
  | motif 2 -> expression 2
  ...
  | _ -> expression n

  vaudra expression 1 si u est du motif 1, expression 2 si u est du motif 2, etc... sachant que l'avantage c'est que tu pourra utiliser les éléments du motif dans tes expressions (par contre c'est pas le cas avec le tiret, qui est l'équivalent d'un "else", à savoir "dans tous les autres cas". (je suis pas très clair donc il vaut mieux que tu te reportes au manuel, ça sera plus rigoureux)

Voici un exemple de code pour ton algorithme en Caml-Light :

Code :

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

1
2
3
4
5
6
7
let rec triee l p = 
  match l with
  | [] -> true
  | [a] -> true
  | a::b::t -> if (p a b) = false then false
               else triee (b::t) p
;;

Si jamais tu ne veux pas avoir à redonner p comme argument à chaque fois, tu peux le définir de manière globale et le virer de la liste des arguments... Par exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
let p x y = 
  if x <= y then true
  else false
;;
 
let rec triee l = 
  match l with
  | [] -> true
  | [a] -> true
  | a::b::t -> if (p a b) = false then false
               else triee (b::t)
;;
 
#triee [1;2;4;5;7];;
- : bool = true
 
#triee [1;2;4;5;4;8];;
- : bool = false

Enfin une dernière remarque mais je ne sais pas si elle est pertinente : c'est que je pense qu'il y a d'autres manières plus simples de vérifier si une liste est triée (ceci dit comme celle que j'ai en tête fait appel à une référence et que l'emploi de références est vivement déconseillé aux débutants, il est possible que je dise une grosse connerie )

EDIT : ah oui et comme le dit bluestorm, pour l'indentation tu vas vite dépasser les 80 colonnes !

[guipe]

Je ne comprends pas trop la syntaxe a::b::t, a est l'élément de tête ? b est le second ? et t c'est le reste ?

[gasche]

Que ce soit dans les motifs ou dans les expressions, '::' est associatif à droite : a::b::c veut toujours dire a :: (b::c).

Ensuite, la syntaxe des motifs sur les listes est bien p::p, où les deux p peuvent être n'importe quel pattern. Par exemple on peut écrire _::_ (pattern universel _), h::_ ou _::t (patterns variables), (a, b)::t (pattern couple), etc. a :: (b::_) est juste un pattern :: dont le pattern imbriqué à droite utilise aussi le constructeur '::'.

En résumé : oui, a :: (b::c) filtre une liste dont le premier élément est a, et dont la queue est une liste dont le premier élément est b, et le reste c.

[guipe]

Merci à vous !

[Steki-kun]

[*]Essaie de suivre le "squelette" donné par Steki-kun ainsi que ses conseils. Néanmoins j'avoue que je ne comprend pas trop son code puisqu'il ne prend que p comme argument (p serait donc la liste, mais alors il n'y aurait pas de fonction de comparaison ??).

J'utilise function à la place de match, function est comme un fun suivi d'un match si tu veux, donc ma fonction n'a qu'un argument apparent (la fonction de comparaison p), mais elle retourne une fonction (qui elle prend une liste), donc on a bien une fonction à 2 arguments, d'abord p et ensuite la liste.

Voici un exemple de code pour ton algorithme en Caml-Light :

Code :

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

1
2
3
4
5
6
7
let rec triee l p = 
  match l with
  | [] -> true
  | [a] -> true
  | a::b::t -> if (p a b) = false then false
               else triee (b::t) p
;;

Décidément, on ne me lit qu'à moitié Je suis désolé mais quand je vois un test "= true" ou "= false" sur un booléen, je crise Je propose de récrire ton code comme ceci:

Code :

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

1
2
3
4
let rec triee p = function
  | [] -> true
  | [_]-> true
  | a::b::t -> p a b && triee p (b::t)

C'est plus lisible avec un && n'est-ce pas ? On pourrait aussi utiliser un pattern 'as' pour éviter de reconstruire b::t dans la deuxième branche mais bon c'est pas important pour un début.

Enfin une dernière remarque mais je ne sais pas si elle est pertinente : c'est que je pense qu'il y a d'autres manières plus simples de vérifier si une liste est triée (ceci dit comme celle que j'ai en tête fait appel à une référence et que l'emploi de références est vivement déconseillé aux débutants, il est possible que je dise une grosse connerie )

Je vois pas comment on peut faire une fonction plus simple que la fonction "triee" ci-dessus. Dans le pire cas (ie. qd la liste est triée) elle fait (n-1) comparaisons où n est la taille de la liste, et c'est le minimum qu'il faille faire pour vérifier qu'une liste est triée. En plus && est paresseux donc on s'arrête dès qu'on peut, et du même coup l'appel récursif est terminal.

S.

[gasche]

Proposition semi-sérieuse (plus "astucieuse" que "simple") utilisant la fonction for_all2 de la bibliothèque List étendue par Batteries :

Code :

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

let sorted p li = try List.for_all2 p li (List.tl li) with _ -> true

Je n'aime pas beaucoup la nécessité du try..with, mais c'est une limitation de la bibliothèque actuelle.

Objectivement je pense que la solution suggérée par Steki-kun est la meilleure.

[Steki-kun]

Si vraiment tu veux utiliser un itérateur, et standard qui plus est, tu peux toujours faire un fold où l'accu est juste l'élément vu au coup d'avant il faudra aussi un raise et un try pour sortir dès que la condition sera devenue fausse, mais bon.

Code :

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

1
2
3
4
5
6
7
8
 
let sorted p l = try 
    ignore (List.fold_left (fun po v -> match po with 
			        | None -> Some v 
			        | Some pre -> if p pre v then Some v
				                    else raise Exit));
    true
    with Exit -> false

C'est marrant d'obfusquer du code ^^ et de détourner des exceptions réservées à la librairie

[gasche]

Hum. La différence c'est quand même que mon code est lisible, alors que le tien ne l'est pas.

Par ailleurs, Exit n'est pas réservée aux fonctions de la bibliothèque, au contraire :
http://caml.inria.fr/pub/docs/manual...ervasives.html

The Exit exception is not raised by any library function. It is provided for use in your programs.

Une version lisible de ton code :

Code :

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

1
2
3
4
5
open List
let is_sorted p li =
  li = [] ||
  try fold_left (fun old e -> assert (p old e); e) (hd li) (tl li); true
  with Assert_failure _ -> false

Code :

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

1
2
3
4
5
let is_sorted p li = function
| [] -> true
| hd::tl -> 
  try fold_left (fun old e -> assert (p old e); e) hd tl; true
  with Assert_failure _ -> false

[Steki-kun]

Hum. La différence c'est quand même que mon code est lisible, alors que le tien ne l'est pas.

Euh, c'était plutôt une preuve de non-concept... j'aurais dû intituler mon post "De la mauvaise utilisation d'itérateurs du premier ordre". Le tien avait le mérite de l'astuce et de la concision, mais bon je pense qu'on est d'accord que c'est pas une très bonne idée dans le cas présent de faire comme ça

Par ailleurs, Exit n'est pas réservée aux fonctions de la bibliothèque, au contraire :
http://caml.inria.fr/pub/docs/manual...ervasives.html

Héhé c'est marrant ça, c'est un acte manqué, je pensais mettre "Not_found" comme font 95% des gens qui utilisent Not_found à toutes les sauces, et le naturel est revenu au galop. Oups, au temps pour moi !

[drunkskater]

J'utilise function à la place de match, function est comme un fun suivi d'un match si tu veux, donc ma fonction n'a qu'un argument apparent (la fonction de comparaison p), mais elle retourne une fonction (qui elle prend une liste), donc on a bien une fonction à 2 arguments, d'abord p et ensuite la liste.

Ok, c'est pas la première fois qu'on m'en parle mais je ne l'ai jamais utilisée (je suis habitué aux match). Est-ce que ça présente un réel intérêt (du genre plus simple à lire pour les gens habitués, plus efficace...) ou est-ce que c'est juste que c'est plus concis (auquel cas je resterai avec mes matchs)

Décidément, on ne me lit qu'à moitié Je suis désolé mais quand je vois un test "= true" ou "= false" sur un booléen, je crise

Ah ouais nan mais t'as raison de criser, c'est complètement con ce que j'ai fait En plus c'est une erreur que je fais assez fréquemment et dont je m'étais déjà rendu compte, mais rien à faire, je sais pas pourquoi. (sans doute à cause de la façon de penser "Si ... est vrai")

Je vois pas comment on peut faire une fonction plus simple que la fonction "triee" ci-dessus. Dans le pire cas (ie. qd la liste est triée) elle fait (n-1) comparaisons où n est la taille de la liste, et c'est le minimum qu'il faille faire pour vérifier qu'une liste est triée. En plus && est paresseux donc on s'arrête dès qu'on peut, et du même coup l'appel récursif est terminal.

Pas plus simple au sens meilleur complexité mais plus simple à lire, mais finalement ça ne l'est pas : plutôt que de faire un filtrage avec a::b::t, faire un filtrage sur h::t en gardant la tête précédente dans une référence. Mais en fait c'est pas plus clair à lire et surtout c'est assez galère pour créer la référence si on veut une fonction qui puisse s'appliquer à plusieurs types d'éléments et qui travaille selon un ordre strictement croissant. Donc idée de merde.

Sinon quand j'avais dû écrire cette fonction en TD j'avais bien entendu fait une référence sur ma liste pour ensuite pouvoir dépiler et comparer à chaque fois la tête de la liste à l'élément le plus grand (= tête précédente si tout va bien) qui était stocké dans une référence. Ca devait donner un truc du genre :

Code :

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

1
2
3
4
5
6
7
8
9
let triee liste comparaison =
  let pile = ref liste and prec = ref (hd liste) and reponse = ref true in
  while reponse && (!pile <> []) do
     reponse := comparaison (!max) (hd !pile);
     max := hd !pile;
     pile := tl !pile
  done;
  !reponse
;;

Mais maintenant c'est vrai que ça me semble très moche !

[Steki-kun]

Ok, c'est pas la première fois qu'on m'en parle mais je ne l'ai jamais utilisée (je suis habitué aux match). Est-ce que ça présente un réel intérêt (du genre plus simple à lire pour les gens habitués, plus efficace...) ou est-ce que c'est juste que c'est plus concis (auquel cas je resterai avec mes matchs)

Non c'est pas plus efficace mais je trouve ça plus simple à lire, et ça me semble mieux refléter le fait que la fonction est définie par cas (peut-être je suis un peu influencé par SML ou Haskell cela dit). J'y vois un avantage pratique c'est de gagner un niveau d'indentation

Code :

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

1
2
3
4
5
6
7
 
let triee p = function
  | _ -> bla..
 
let triee p l =
  match l with
    | _ -> bla

Evidemment, on peut aussi coller le match l with sur la première ligne:

Code :

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

1
2
3
 
let triee p l = match l with
  | _ -> bla..

mais quand je vois "let f ... l = match l with" j'ai limpression de voir une eta-expansion (un truc de la forme "let f ... x = g ... x") et je vois pas pourquoi ne pas mettre function.

Maintenant il se peut que l ne soit pas le dernier argument au cas où ça ne marche pas, mais justement dans 99% des cas l'argument que la fonction commence par détruire est celui qui devrait être logiquement en dernier donc utiliser function peut éviter de mettre les arguments dans un sens pas très logique. Par ex, autant guipe que toi avez écrit la fonction triée avec comme arguments d'abord la liste puis le prédicat, mais ça me semble illogique: il y a beaucoup plus de chance que tu utilises la même fonction de comparaison pour comparer diverses listes, plutôt que de comparer la même liste avec diverses fonctions de comparaison différentes... C'est toujours bien de penser à l'avance aux applications partielles qui pourront servir.

Code :

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

1
2
3
4
5
6
7
8
9
let triee liste comparaison =
  let pile = ref liste and prec = ref (hd liste) and reponse = ref true in
  while reponse && (!pile <> []) do
     reponse := comparaison (!max) (hd !pile);
     max := hd !pile;
     pile := tl !pile
  done;
  !reponse
;;

Mais maintenant c'est vrai que ça me semble très moche !

Oui assez, mais on perd vite ce genre de mauvaises habitudes Au passage, elle raise Failure sur une liste vide cette fonction ^^

S.

[Cacophrene]

Bonjour,

Ceci est de l'humour.
Puisque vous avez proposé diverses solutions plus ou moins obscures à l'aide d'ingrédients variés, je vais vous en proposer une autre qui est à la fois concise, illisible et abominable . Voici les idées maîtresses du code :

• Utiliser un fold_left, mais sans lever d'exception (ça c'est crédible).
• Stocker l'élément précédent grâce à une référence (c'est déjà moins bien).
• Exploiter l'évaluation de droite à gauche de caml (carrément abominable, en fait il me semble que la doc précise que l'ordre est non spécifié).

Ce qui donne ceci :

Code :

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

1
2
3
4
5
 
let triee p = function
  | [] -> true
  | x :: t -> let r = ref x in
    List.fold_left (fun res y -> snd ((r := y), res && p !r y)) true t

Si vous rencontrez quelqu'un pour qui cette écriture est évidente, même si c'est une fille et qu'elle est jolie, surtout n'hésitez pas : fuyez.

Cordialement,
Cacophrène

[gasche]

Avec le module BatRef de Batteries :

Code :

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

1
2
3
4
5
open BatStd
let triee p = function
  | [] -> true
  | x :: t -> let r = ref x in
    List.fold_left (fun res y -> res && p (BatRef.post r (const y)) y) true t

Un inconvénient de cette fonction est qu'elle parcourt toujours la liste entièrement.

Code :

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

1
2
3
4
5
open BatStd
let triee p = function
  | [] -> true
  | x :: t -> let r = ref x in
    List.for_all (fun y -> p (BatRef.post r (const y)) y) t