Discussion :

[BlueJack]

Bonsoir,

Je m'entraine (étant un gros débutant) sur les listes pour pouvoir je l'espère bientot, implémenter des algorithmes de tri en OCaml. Pour cela j'ai regardé des tps/ tds sur le net en essayant de faire quelques exercices.

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
19
20
 
(* Taille d'une liste *)
let rec size = function
  |[] -> 0
  |h::q -> 1 + (size q);;
 
(* Est dans une liste *)
let rec inl x = function
  |[] -> false
  |h::q -> if t = x then true else (inl x q);;
 
(*ajouter à la fin*)  
let rec add x = function
  |[] -> [x]
  |h::q -> h::(add x q);;
 
(*somme d'une liste *)
let rec somme = function
  |[] -> 0
  |h::q -> h + (somme q);;

Auriez vous des idées de nouveaux exercices?
Je dois vous avouer que je suis bloqué au mirroir (inverser une liste), et à l'insertion d'un nombre dans une liste ordonné.

Bonne soirée

[Cacophrene]

Salut !

D'abord quelques remarques sur les codes que tu nous donnes, avec des idées d'exercices qui en découlent :

Fonction size : Sais-tu quel est le comportement de cette implémentation lorsqu'on lui donne une très longue liste (par ex. 500 000 éléments) en entrée ? Si ce n'est pas le cas, tu peux tester avec make (création de liste) :

Code :

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

1
2
3
4
5
6
let make n x =
  let rec loop res i =
    if i < n then loop (x :: res) (i + 1)
    else res
  in loop [] 0

Idée d'exercice : réécrire size pour éviter ce comportement. Au besoin s'inspirer de la fonction make donnée ci-dessus. Comment appelle-t-on les fonctions écrites de cette manière ?

Fonction inl (communément appelée mem) : OCaml dispose d'opérateurs booléens OU (noté ||) et ET (noté &&) paresseux. En conséquence : dans A OU B, B n'est évalué que si A est faux; dans A ET B, B n'est évalué que si A est vrai.

Idée d'exercice : peut-on exploiter la propriété de l'opérateur OU pour écrire autrement la fonction inl ? Comment faire pour que la fonction de comparaison utilisée puisse être choisie par l'utilisateur ? Comment appelle-t-on une fonction qui reçoit une autre fonction en entrée ? Connais-tu d'autres fonctions de ce type ?

Fonction add (en fait ce serait append par opp. à prepend) : Même problème que la fonction size.

Idée d'exercice : Peut-on faire autrement ? Quelle est la conséquence d'une écriture « à la make (ci-dessus) » ? Que faut-il en conclure sur la stratégie d'insertion dans une liste en OCaml ?

Fonction somme : exactement la même chose que size.

Je dois vous avouer que je suis bloqué au mirroir (inverser une liste)

Avec ce que tu as dû observer si tu as essayé de réécrire add comme indiqué plus haut, tu dois savoir comment faire.

insertion d'un nombre dans une liste ordonnée

Faut-il déterminer cette relation d'ordre ? Si oui, est-ce possible quel que soit le contenu de la liste ?

Cordialement,
Cacophrène

[BlueJack]

Merci énormément pour ta réponse je vais essayer de faire tout ça aujourd'hui et je viendrai mettre mes résultats

Bonne journée

[gasche]

Comme exercice sur les listes, tu peux recoder l'ensemble des fonctions du module List : documentation du module List.

Pour la fonction "rev" qui inverse les listes, tu devrais commencer par coder une fonction intermédiaire plus simple à trouver : c'est la fonction "renverse_dans", qui prend en paramètres deux listes "a" et "b", et qui ajoute à "b" tous les éléments de a, un par un (indice : faire une récursion en faisant un filtrage sur "a").

[tydaldus]

- réécrire la fonction somme en utilisant la fonction List.fold_left

[InOCamlWeTrust]

Plus simple : écrire une fonction de concaténation (la même chose que @) récursive terminale, c'est-à-dire pouvant fonctionner correctement avec n'importe quel nombre d'éléments.

[BlueJack]

Bonsoir,

J'ai beau me retourner la tête dans tous les sens, rien y fait. Tous ces exercices j'arrive a les faire en C ou encore Java, mais en OCaml je sais pas pourquoi, je n'ai aucun déclic. J'ai passé toute ma journée avec un crétarium et mon cahier de brouillon mais non, je sais pas ma logique est surement très mauvaise.

[gasche]

Pour la fonction "rev" qui inverse les listes, tu devrais commencer par coder une fonction intermédiaire plus simple à trouver : c'est la fonction "renverse_dans", qui prend en paramètres deux listes "a" et "b", et qui ajoute à "b" tous les éléments de a, un par un (indice : faire une récursion en faisant un filtrage sur "a").

Code ocaml :

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

1
2
3
let rec renverse_dans a b = match a with
| [] -> b
| tete::queue -> renverse_dans ... ...

Tu peux le faire !

[BlueJack]

J'ai reussi à mettre un élément dans une liste trié.

Code :

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

1
2
3
4
5
let rec add x list  =
  match list with
  |[] -> x :: list
  |head :: queue -> if x < head then x :: list
  			 else add x queue;;

Si x est inférieur à la tête, j'ajoute x et head :: queue soit list. Malheuresement il ne me retourne que ce qu'il y a après l'ajout.
Comment faire pour qu'il me récupère le bout de liste avant? Je vois toujours pas car avec la récursion ce qui a avant est 'coupé' non?

Je me lance dans ton exo BlueStorm!
Comment faire pour atteindre la liste de b? b[x]?
Merci encore pour votre aide.