Discussion :

[Amnael]

Bonsoir,

j'éprouve quelques difficulté à réaliser la fonction suivante

la fonction doit prendre deux listes de couples.
La fonction devra retourner une liste de couples tels quel le premier élément de la liste 1 est aussi un second élément de la liste 2.

Sauf que, je ne sais pas comment je peux m'en sortir pour sauvegarder mon résultat après chaque passage

Concrètement j'ai un truc de ce style

Code :

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

1
2
3
4
5
let rec composition = fun l1 -> fun l2 ->
	match l2 with
	| [] -> []
	| (a,b)::l22 -> if(appartient b l1) then  ...
					else composition l1 l22;;

avec appartient qui me permet de savoir si l'élément b apparaît en tant que premier élément de la liste de couple

en gros


appartient 1 [(2,1);(1,4)] renvoit true
appartient 1 [(2,1);(3,4)] renvoit false

Il me faudrait soit réussir à supprimer les éléments de l1 qui ne correspondent pas, soit reconstruire une liste de zéro mais sans changer l1 et l2 pour ne pas fausser le résultat final...et là en restant purement fonctionnel je vois pas du tout comment je peux faire ça...

[SpiceGuid]

Code Ocaml :

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

fun list1 list2 -> ...

Il n'y a rien qui puisse obliger le premier élément de la liste 1 d'être également le second élément de la liste 2. D'ailleurs il n'y a rien qui puisse obliger list2 à posséder deux éléments.

[Amnael]

Code Ocaml :

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

fun list1 list2 -> ...

Il n'y a rien qui puisse obliger le premier élément de la liste 1 d'être également le second élément de la liste 2. D'ailleurs il n'y a rien qui puisse obliger list2 à posséder deux éléments.

Je n'ai pas compris votre commentaire..

Le nombre d'élément des listes on s'en fiche.
Seulement les éléments des listes sont des couples.

Pourquoi ?

il me semble que le typage est assez clair le pattern matching sur la liste l2 montre très clairement que l'on extrait un couple de la liste et donc que l2 contient des couples. Si ce n'est pas le cas c'est que la liste est vide.

La liste l1 se construit sur le même principe puisque appartient fait appel en second argument à une liste de couple.

Donc obligatoirement les deux listes sont des listes de couples il n'y a aucune raison d'en douter. D'où mon incompréhension quand à votre message.



Pour clarifier l'algo:


Pour chacun des éléments (de la forme a*b donc) de la liste 2.
Je compare l'élément b courant avec chacun des éléments de la forme (c*d) de la liste 1.
- Si b=c je met (c,d) dans une liste (disons l3) puis je passe à l'élément suivant de l2
Sinon je passe juste à l'élément suivant de l2 sans conserver le couple (c,d)
Fin Pour


Voilà ce que je dois faire.

Sauf que, je ne sais pas comment récupérer le résultat en restant purement fonctionnel.

[DocBS]

On pourrait faire quelque chose comme

Code :

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

1
2
3
4
5
6
 
let rec composition l1 l2 =
  match l2 with
  	|[]->[]
  	|m::mx-> let (a,b)=m in
           if (appartient b l1) then (a,b)::(composition l1 mx) else (composition l1 mx);;

dans ce cas la liste résultante est construite de façon récursive à partir des éléments de la liste l2.

Si l'on veut récupérer les éléments de la liste l1, il faudrait écrire :

Code :

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

1
2
3
4
5
6
 
let rec composition l1 l2 =
  match l1 with
  	|[]->[]
  	|m::mx-> let (a,b)=m in
           if (is_second a l2) then (a,b)::(composition mx l2) else (composition mx l2);;

où la fonction is_second vérifie si l'élément a figure quelque part en 2e position dans la liste l2.