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.

[gasche]

Dans ton code, tu considères le filtrage sur "head :: tail", mais tu n'utilises plus la variable "head" dans ce que tu renvoies, alors que c'est le content du premier élément de la liste. Il faut que tu conserves "head" dans ta valeur de retour, quelque part (à toi de voir où l'ajouter et comment).

Je ne comprends pas ta question (b[x] ça n'existe sûrement pas), et je précise que tu dois ajouter les éléments de 'a' au début de 'b' (au cas où ce ne serait pas clair) : il suffit de faire "x :: b" pour ajouter un élément quelconque 'x' à b.

[BlueJack]

Code :

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

1
2
3
4
let rec inlist a b =
  match a with
  |[] -> b
  |h::t -> h::(inlist t b);;

Cela donne:
# inlist [1;2;3;4] [];;
- : int list = [1; 2; 3; 4]

Etait ce bien cela?

[gasche]

Non justement, là tu as codé la concaténation simple; c'est utile, mais ce n'est pas ce qu'on veut, puisque ça n'aide pas à renverser une liste : on voudrait que quand tu fais "renverse_dans a b", les éléments de a se retrouvent en tête de b, mais dans l'ordre inversé : le premier élément de a est placé juste avant le premier élément de b, puis le deuxième élément est placé encore avant (en tête), etc.

[Cacophrene]

Salut !

BlueJack > tu as tous les éléments en main pour écrire la fonction renverse_dans. Voici un récapitulatif.

on voudrait que quand tu fais "renverse_dans a b", les éléments de a se retrouvent en tête de b, mais dans l'ordre inversé : le premier élément de a est placé juste avant le premier élément de b, puis le deuxième élément est placé encore avant (en tête), etc.

Juste pour fixer les idées avec un exemple simple, si on choisit les listes a = [1; 2; 3] et b = [4; 5; 6], on voudrait que la fonction renverse_dans appliquée à a et b renvoie [3; 2; 1; 4; 5; 6].

De plus bluestorm t'a déjà donné la forme générale de la fonction (cf. ci-dessous). Il n'y a qu'à remplacer les points de suspension par quelque chose.

Code :

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

1
2
3
4
5

let rec renverse_dans a b = 
  match a with
    | [] -> b
    | head :: tail -> renverse_dans ... ...

Et en prime tu as une piste :

il suffit de faire "x :: b" pour ajouter un élément quelconque 'x' à b

Cordialement,
Cacophrène

[BlueJack]

Merci beaucoup je ressort mon cahier de brouillon et vous poste ce que j'ai fais ce soir J'ai choisi ce langage pour essayer de faire un petit projet sur du sequençage de molécule d'ADN, et d'autres projets en biologie. Merci encore!

[EDIT] Je vous donne des infos sur mes recherches:
Imaginons que j'ai une deux listes [1;2] et [3], la liste final doit être [2;1;3].
C'est à dire, [dernierElementA;...;premierElementA;B]. Pour mettre en pratique cela j'ai pensé utilisé la recusivité sur A afin d'atteindre le dernier élément, puis remonter en ajoutant au fur et à mesure les éléments trouvé à B puis ajouté B. Voici le schéma en gros:

Recursivité:
1
2
-> STOP maintenant on remonte!
2 :: b
1 :: b
b (soit 3)

J'éssais de réaliser tout ça, pour l'instant avec ce code mais sans succès.

Code :

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

1
2
3
4
let rec renv a b =
   match a with
   |[] -> b
   |t::q -> (renv q b)::b;;

[gasche]

Non, ça ne marche pas : quand tu écris "x :: y", il faut que le x soit un élément, et le y une liste. Dans ton code, ((renv ...) :: b) ne peut pas marcher.

[BlueJack]

Cela signifie donc que je dois ajouté h à b et rappeler la fonction avec t et b?

Code :

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

1
2
3
4
let rec renv a b =
   match a with
   |[] -> b
   |t::q -> let x = t::b in renv q x;;

Pardonnez moi, j'ai du mal à penser fonctionnel je pense.

[gasche]

Oui, c'est ça. Maintenant tu obtiens "rev", qui renverse une liste, gratuitement :

Code :

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

1
2
3
4
5
let rev liste =
  let rec renv a b = match a with
    | [] -> b
    | hd::tl -> renv tl (hd::b) in
  renv liste []

On peut ré-écrire en inversant les paramètres de "renv" :

Code :

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

1
2
3
4
5
let rev liste =
   let rec rev_aux acc = function
   | [] -> acc
   | hd::tl -> rev_aux (hd::acc) tl in
   rev_aux [] liste

Commence par vérifier que ce sont bien les mêmes fonctions (j'ai renommé "renv" en "rev_aux", comme "fonction auxiliaire pour coder 'rev'", et changé le nom des arguments).

Est-ce que tu peux coder List.fold_left ? Son comportement est décrit dans la documentation (j'ai déjà donné le lien) et c'est une fonction assez proche de "rev" (en fait rev est un cas particulier de fold_left).


Ah, et arrête de geindre sur "je n'arrive pas à penser fonctionnel". Il n'y a pas de "pensée fonctionnelle" mais des principes et réflexes qu'on acquiert avec la pratique. C'est comme les gens qui expliquent qu'ils "ne sont pas fait pour les maths" pour décrire leurs à priori sur la discipline et leur absence d'efforts de compréhension.

[BlueJack]

Oui, c'est ça. Maintenant tu obtiens "rev", qui renverse une liste, gratuitement:

Comment fais tu pour penser à ca aussi facilement?

Commence par vérifier que ce sont bien les mêmes fonctions (j'ai renommé "renv" en "rev_aux", comme "fonction auxiliaire pour coder 'rev'", et changé le nom des arguments).

Je vais chercher de la documentation sur les accumulateurs.

Est-ce que tu peux coder List.fold_left ? Son comportement est décrit dans la documentation (j'ai déjà donné le lien) et c'est une fonction assez proche de "rev" (en fait rev est un cas particulier de fold_left).

Je me met au travail!

Ah, et arrête de geindre sur "je n'arrive pas à penser fonctionnel". Il n'y a pas de "pensée fonctionnelle" mais des principes et réflexes qu'on acquiert avec la pratique. C'est comme les gens qui expliquent qu'ils "ne sont pas fait pour les maths" pour décrire leurs à priori sur la discipline et leur absence d'efforts de compréhension.

Chef, oui chef!

[BlueJack]

Voici mon code:

Code :

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

1
2
3
let rec myFold s x = function
  |[] -> x
  |h::t -> myFold s (s x h) t;;

Pourquoi ce code?
Il faut donc que j'additionne chaque nombre de la liste à x.
J'ai lu il y a deux jours que (+ 1 2) signifie 1 + 2.
A partir de ça x est calculer avec h grâce au signe s, et j'envois la queue de la liste a chaque tour pour traîter les éléments un par un.

[Cacophrene]

Salut !

Il faut donc que j'additionne chaque nombre de la liste à x.
J'ai lu il y a deux jours que (+ 1 2) signifie 1 + 2.
A partir de ça x est calculer avec h grâce au signe s, et j'envois la queue de la liste a chaque tour pour traîter les éléments un par un.

Ton code est bon, mais je ne comprends pas bien pourquoi tu parles d'addition dans ton message (il doit me manquer le contexte). Est-ce que c'est ce cas particulier qui t'a permis d'apprivoiser fold_left ? Quoi qu'il en soit, il ne t'aura pas échappé que List.fold_left est en fait une fonction très générale aux applications variées.

Juste une petite remarque, même si ça ne change rien à la validité du code, il n'est pas sans intérêt de respecter certaines conventions pour les noms des variables, comme f pour une fonction (c'est tout con mais bien utile). Je suppose que le s que tu utilises dans ton code était là pour « somme ».

Code :

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

1
2
3
4
let rec fold_left f ini = function
  | [] -> ini
  | x :: tail -> fold_left f (f ini x) tail

En tout cas, l'objectif est atteint. Bravo

Cordialement,
Cacophrène