Discussion :

[MadEye]

Bonjour,
j'ai un problème dont j'ai du mal à trouver seul la solution...

Le principe : je dois trouver un élément (n'importe lequel mais il est sans doute unique) dans une liste qui vérifie une relation avec tous les autres éléments de la liste.

J'ai essayé d'utiliser une fonction auxiliaire dont un argument sera à donner dans la fonction finale récursive, mais j'ai toujours un TopLevel input avec
This expression has type.. ..but is used with type.. :

Code :

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

1
2
3
4
let rec min_p o a = fun
| _ [] -> failwith("pas de min >> ce cas ne doit pas arriver normalement")
| (o) (t::q) -> if aux o t a = true then (t,q)
else min_p o q ;;

a est la liste en question ;
o est un argument nécessaire pour la fonction aux ;
aux est une fonction récursive qui renvoit true si l'élément t est en relation avec tous les éléments de a (relation d'ordre totale du style <= )


Je sens que ce problème est lié au fait que le test aux o t a = true est déjà un test récursif ou quelque chose comme ça...

Pourriez-vous m'éclairez (sur le principe de fonctionnement d'un tel algo) s'il vous plaît ?

Merci d'avance!

[gasche]

Code :

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

1
2
3
4
let rec min_p o a = fun
| _ [] -> failwith("pas de min >> ce cas ne doit pas arriver normalement")
| (o) (t::q) -> if aux o t a = true then (t,q)
else min_p o q ;;

"o" et "a" n'ont aucun sens. Il faut donner un nom compréhensible à tes variables, sinon on ne peut pas vraiment aider.

que fait "| (o) (t::q) " ?

Le principe : je dois trouver un élément (n'importe lequel mais il est sans doute unique) dans une liste qui vérifie une relation avec tous les autres éléments de la liste.

Si tu veux vraiment faire ça, je te conseille d'écrire une fonction auxiliaire qui renvoie pour une liste contenant, pour chaque élément de la liste, le couple (élément, liste privée de cet élément).

Cependant, cette méthode est quadratique (c'est une complexité inhérente à ta définition : si pour tout élément on teste un prédicat sur tous les autres, ont a forcément au mieux du quadratique).
Pour la plupart des prédicats simples (par exemple "est le minimum de la liste", que suggère ton code avec ses "min"), il existe des méthodes plus efficaces (ici, linéaires).

[MadEye]

D'abord, merci de ta réponse

C'est vrai que tout cela n'est pas très clair, c'est parce que j'ai voulu simplifier l'énoncé et au final ça donne quelque chose d'incompréhensible...

partons du plus basique :
on cherche le plus petit élément d'une liste li.

Comment procède-t-on ?

Intuitivement, j'aurais envie de prendre le premier élément pour savoir si c'est le plus petit élément : tant que le test <= est vrai, on continue puis on sort de la récursivité par le cas simple liste vide : [] -> true
si une fois le test est faux, on continue la première récursivité en testant le deuxième élément de la liste ( ex: t::t2::q on teste t2) mais le problème c'est que de ce fait on écarte la tête t du test <=...

Sinon en suivant ton conseil de fonction auxiliaire, je ne vois pas trop où cela nous mène... (désolé je suis embrouillé)

[gasche]

Ok, c'est plus clair quand on sait ce que tu cherches.

Maintenant, je pense aussi avoir compris ce que tu as essayé de coder.
Tu voulais faire quelque chose du genre (attention, pseudo-code horrible) :

Code :

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

1
2
3
minimum :
|  [] -> pas de minimum
|  h::t -> si h est plus petit que tous les éléments de t, alors h, sinon minimum t

C'est ça ?

Si oui, je pense qu'en clarifiant un peu ta pensée, tu devrais pouvoir faire un truc qui marche (en virant le deuxième argument, par exemple). Si tu y as droit, la fonction for_all : ('a -> bool) -> 'a list -> bool de la bibliothèque standard (définie ici) pourrait t'aider.

Cependant, il existe une manière beaucoup plus rapide de calculer le minimum d'une liste.
Regarde la liste suivante : 39 42 71 21 65 91 22 31 15 57 83 3 55
Quel est son minimum ? Comment as-tu fait pour le voir ? Est-ce qu'une fois que tu as lu 39, tu as ensuite lu tous les éléments pour vérifier que c'était bien le minimum, et tu es ensuite reparti au niveau du 42 ?
Essaie de comprendre comment tu fais, et demande à l'ordinateur de faire pareil.

[InOCamlWeTrust]

Je crois qu'utiliser (ou faire utiliser) des itérateurs, prédicat ou autres, embrouille plus qu'autre chose. La recherche du minimum d'une liste, ça se fait en une seule passe !

Il existe une façon très élégante, optimale en termes de complexité temporelle, et très simple de calculer le minimum ou le maximum d'une liste. En pseudo-code :

Code :

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

1
2
3
4
 
minimum :
  | x :: [] -> x
  | x :: queue -> si x est plus petit que le minimum de queue, alors ... sinon ...

Cette fonction a le gros désavantage de ne pas être récursive terminale. Pour faire une fonction récursive terminale, il faudrait passer par une fonction auxiliaire.

[MadEye]

Ah, merci, on commence à y voir plus clair...

Effectivement, on n'a pas besoin de revenir en arrière, dès qu'on trouve un plus petit, on prend celui là pour continuer... du coup on n'a qu'un parcours de la liste à faire.

J'ai écrit un bout de code mais j'ai encore une fois le même problème, à savoir garder cet élément à comparer au fur et à mesure de la récursivité... :

Code :

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

1
2
3
4
5
 
let rec mini_aux li t2 = function
 [] -> failwith"pas de mini"
| t::q -> if t2 <= t then (mini_aux q t2)
 else (mini_aux q t) ;;

merci encore..

[MadEye]

Oui effectivement ça a l'avantage d'être beaucoup plus court !
Par contre, je ne suis pas sûr du " else mini q " :

Code :

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

1
2
3
let rec mini li = function
 [x] -> x
| x::q -> if x <= mini q then x else mini q ;;

argh j'ai vraiment du mal avec ça...

PS: en tout cas, j'ai toujours le même type d'erreur :

This expression has type 'a list -> 'a list -> 'a,
but is used with type 'a list -> 'a.

[gasche]

Attention, ton filtrage n'est pas exhaustif, tu ne vérifies pas le cas [].

Si tu utilises "function", l'argument est implicite, il ne faut pas le nommer. Remplace "let rec mini li = function" par "let rec mini = function". Le type te disait "la fonction prend deux listes en argument, et vous ne lui en donnez qu'une".

Par ailleurs, ton algo a un grave problème de copmlexité : tu appelles deux fois "mini q" (je te laisse calculer la complexité que tu obtiens, si ça t'intéresse). Il faut que tu stockes ce résultat intermédiaire avec un "let ... = .. in".

[MadEye]

Ouf ça y est j'ai enfin réussi à avoir quelque chose qui fonctionne :

Code :

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

1
2
3
4
let rec mini = function
 [] -> failwith"pas de mini"
| [x] -> x
| x::q -> let mini_q = mini q in if x <= mini_q then x else mini_q ;;

maintenant il me reste à adapter la méthode à mon exercice, un peu plus tordu que ça il faut avouer...

Merci beaucoup !! je reposte au besoin

[gasche]

Hum, au cas où ça t'intéresse, voilà le code dont je parlais pour la vérification des prédicats : il renvoie la liste des couples (élément, liste privé de l'élément) :

Code :

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

1
2
3
4
5
let extractions li =
  let rec extractions avant = function
    [] -> []
  | elem::apres -> (elem, avant @ apres) :: extractions (elem::avant) apres
  in extractions [] li

Avec ça, tu peux faire ta première version compliquée de minimum :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
let minimum liste =
  let rec for_all p = function
    [] -> true
  | hd::tl -> p hd && for_all p tl
  in
  let rec filter p = function
    [] -> []
  | hd::tl -> (if p hd then [hd] else []) @ filter p tl
  in
  let elems = extractions liste in
  fst (hd (filter (fun (a, reste) -> for_all (fun b -> a < b) reste) elems))

(les fonctions filter (nommée find_all en Caml Light) et for_all existant dans la bibliothèque standard, mais je les ai recodées au cas où tu ne les aurais jamais vues)

Par ailleurs, cette fonction peut servir dans des cas plus crédibles. On peut l'utiliser pour une version naïve du calcul de l'enveloppe convexe d'une liste de points, par exemple.

[MadEye]

Wow je ne saisis pas tout mais c'est tout de suite moins facile d'accès...

En tout cas, je suis arrivé au bout de l'exercice, j'espère que c'est correct!

Je vous remercie beaucoup Bluestorm et InOCamlWeTrust pour votre généreuse aide

[InOCamlWeTrust]

De rien : repasse nous voir dès que tu auras une question, ou une remarque, ou ce quetu veux.