Discussion :

[Trolololz]

Bonjour,
J'ai un petit soucis de compréhension, ou de syntaxe, sur un problème que l'on m'a donné en TD.
Je vous écris le problème comme ça vous le comprendrez.

Ecrire une fonction supprime dont les deux arguments sont des listes l1 et l2 et qui
supprime de la liste l2 les éléments contenus dans la liste l1. (On ne conservera donc de la
liste l2 que les éléments qui ne sont pas dans l1)
si la liste l1 est égale à [3; 5; 2; 1] et la liste l2 à [4; 2; 9], le résultat sera [4; 9]

J'ai retourné le problème dans tous les sens. J'ai crée deux petites fonction.
L'une me permet de supprimer d'une liste un élément que je définit :

Code :

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

1
2
3
4
5
6
7
let s1e l n =
let rec test acc l n = match l with
	|[] -> acc
	|h::t -> if (h=n)
				then test acc t n
				else test (acc@[h]) t n
in test [] l n;;

L'autre me permet de filtrer la tête d'une première liste, dans une deuxième liste. Ce code à l'air plus simple, mais la fonction je l'ai trouvé sur internet, et pas dans le cours, du coup je ne sais pas si cela passe ou pas. Voyez par vous même :

Code :

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

1
2
let filtrer l1 l2 =
List.filter (fun y -> y != (List.hd l1)) l2;;

Entait, le problème se situe au niveau de la compréhension du problème ET de la syntaxe de la fonction récursive.
D'après ce que j'ai compris, il faudrait prendre la tête de la première liste, la filtrer dans la deuxième liste, puis ré appliquer cette fonction sur la queue de la première liste et la deuxième liste déjà filtrée. J'arrives à me le représenter dans la tête, mais c'est très ambigu quand j'essaye de le coder. En fait, je ne sais pas si cette deuxième liste filtrée, je dois la stocker dans un accumulateur, ou bien la garder comme cela.
J'ai réussi à stocker cette deuxième liste dans un accumulateur, mais à chaque fois que la fonction s'appelle elle même elle rajoute dans l'accumulateur la liste filtrée, du coup quand je renvois acc, cela me fait une liste de ce style : [6;8;4;6;8;4;6;8;4;6]
Vous l'aurez compris, dans le cas précédent j'ai filtré le la liste [4;6;8] par les éléments de la liste [4;3;2;8], mais les listes filtrées se sont collées l'une sur l'autre ...
Voilà, j'espère que quelqu'un aura la courage d'essayer de me faire comprendre tout cela
Je vous remercie par avance.

[SpiceGuid]

À lire l'énoncé tu as besoin de tester l'appartenance d'un élément à une liste, c'est-à-dire une fonction similaire à List.mem.

Ensuite il faut filtrer, c'est-à-dire utiliser une fonction similaire à List.filter.

[Trolololz]

D'abord merci pour la réponse rapide.

Ensuite, j'ai essayé de placer le List.mem, mais comme dit dans mon premier post, c'est la syntaxe qui me pose problème.

Je ne sais pas où placer ma fonction filtrer pour que la fonction supprimer se relance sur t1 l2.

En essayant ça, je tombe toujours sur une liste vide :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
let filtrer l1 l2 =
List.filter (fun y -> y != (List.hd l1)) l2;;

let supp l1 l2 =
let rec aux l1 l2 = match l1 with
	|[] -> l2
	|h1::t1 -> match l2 with
			|[] -> failwith "l2 vide"     <---En l’occurrence, je tombe toujours dans ce cas
			|h2::t2 -> if List.mem h1 l2 then aux t1 (filtrer l1 l2)
							      else aux t1 l2
in aux l1 l2;;

[Jedai]

Je pense que plus que la syntaxe, c'est le raisonnement qui te fait défaut... Supposons que tu partes des outils de base de OCaml, c'est-à-dire les fonctions récursives et le pattern matching, sans connaitre les fonctions disponible dans le module List (a priori, si tu ne les as pas encore vues en cours, ton professeur attend plutôt une solution élémentaire.

Il y a deux façons de travailler ici puisque tu as deux arguments sur lesquels tu pourrais faire une récursion. Dans la suite je vais décomposer selon la forme de l2.

l2 privé de l1 est :

• Soit l2 est vide et le résultat est donc vide,
• soit l2 est h2 :: t2 et le résultat est donc
  
  • si h2 n'est pas dans l1 alors h2 suivi de t2 privé de l1 ,
  • sinon seulement t2 privé de l1

Code :

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

1
2
3
let supprimer l1 l2 = match l2 with 
  | [] -> []
  | h2 :: t2 -> si (h2 est dans l1) alors (supprimer l1 t2) sinon (h2 :: supprimer l1 t2)

A toi d'écrire la condition "h2 est dans l1" (je te conseille de l'écrire à la main, même si tu sais que List contient déjà cette fonction.

Alternativement en décomposant selon la forme de l1 :

Code :

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

1
2
3
let supprimer l1 l2 = match l1 with 
  | [] -> l2
  | h1 :: t1 -> supprimer t1 (l2 sans h1)

Même problème mais cette fois ci, il faut écrire "l2 sans h1".

Mélanger une décomposition selon l1 et une décomposition selon l2 sont la source de ta confusion.

--
Jedaï

[Trolololz]

Effectivement, dit comme ça, ça a l'air plus simple. J'ai appliqué ton deuxième code, ça marche comme sur des roulettes, mais je n'arrive pas à comprendre ton raisonnement derrière cela. Comme tu dis c'est ce qui me fait défaut.
Au sujet de ce qu'on a vu ou pas. On a quasiment parcouru tout ce qui concerne la Programmation Fonctionnelle en Caml, c'est à dire qu'on a vu les listes, et quasiment toutes les fonctions qui vont avec, appart List.filter .
En fait, je suis en période de rattrapages, je révise en faisant les annales. Je suis en première année de Licence Maths Info, premier semestre on a fait du C, mais ce semestre, le Caml m'a tué, j'ai beaucoup de mal à raisonner dans ce langage. En particulier sur les fonctions récursives. J'ai aussi quelques problèmes sur les types, mais ça c'est du à mon manque d'attention en cours à la fin de l'année...
Bref, en tout cas je t'en remercie, cela me permettra d'avancer, si j'ai d'autres problèmes je reviendrais sûrement pour vous prendre la tête encore un peu

EDIT :
Au fait, j'ai oublié mon p'tit bout de code :

Code :

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

1
2
3
4
5
6
7
8
let rec filter l1 l2 = match l2 with
	|[] -> l2
	|h2::t2 -> if (List.hd l1 = h2) then filter l1 t2
		                        else h2::filter l1 t2;;
 
let rec supprimer l1 l2 = match l1 with
	|[] -> l2
	|h1::t1 -> supprimer t1 (filter l1 l2);;

[Jedai]

Il serait plus simple d'écrire ton filtre pour qu'il prenne un seul élément à retirer d'une liste (tu n'utilises pas le reste de l1).

Pour ce qui est du raisonnement pour une fonction récursive, l'idée est de choisir un argument sur lequel on fait la discrimination, de repérer un cas de base, généralement très simple à traiter, puis de traiter le(s) cas général en assumant que la fonction qu'on est en train d'écrire peut être utilisé sur tous les cas plus petit (à toi de choisir une métrique pour définir "plus petit", ici la longueur de la liste) :

Donc ici, en discriminant sur l1, c'est une liste d'éléments à retirer de l2 :

• Si l1 est vide, il n'y a plus d'éléments à retirer, donc le résultat est l2
• Si l1 contient un élément h1 et une liste plus courte t1, il va falloir retirer h1 à l2, puis retirer encore t1 à ce qui reste de l2, mais ça tu sais faire puisque t1 est plus petite que l1, tu peux donc juste utiliser la fonction récursive.
  Reste à savoir retirer h1 de l2, ce qui est un problème différent, et plus simple.

NB : tu peux reconnaitre un fold ici :

Code :

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

1
2
3
let rec fold_left f z xs = match xs with
  | [] -> z
  | (x :: xs) -> fold_left f (f z x) xs

Ce qui dans notre cas est :

Code :

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

1
2
3
let supprimer l1 l2 = 
  let aux r2 e1 = List.filter (fun x -> x <> e1) r2 
  in List.fold_left aux l2 l1

[Trolololz]

Ah d'accord.J'ai cherché un peu pour la fonction fold.
J'ai trouvé ta réponse sur un autre topic (ici)
D'après ce que j'ai compris donc, quand on applique la fonction fold sur une liste, c'est comme si on prenait un livre, on pliait la première page (on applique la fonction "plier" à la première page), puis on passe à la page suivante, on plie cette page (on applique de nouveau la fonction "plier"), etc.
Si j'ai bien compris, c'est exactement ce qu'il me fallait pour cette satanée fonction supprimer.
Du coup, j'ai avancé et à la question suivante ce sont les types qui me posent problème. En fait je ne sais pas comment faire quand on me demande d'appliquer une fonction sur un élément "de type ...".
Dois-je ouvrir un autre sujet pour que ça soit plus lisible ou alors on peut en parler ici ?

[Jedai]

Une question par sujet et vice-versa, c'est mieux pour la visibilité de ta question (celle-ci est marquée résolue) et pour qu'à l'avenir la recherche dans le forum soit efficace.

[Trolololz]

C'est ce que je me suis dit
A tout de suite alors.