Discussion :

[KateA]

bonjour,

je cherche à comprendre l'implementation des listes (simplement chainées) en c.
je ne comprends pas très bien pourquoi l'insertion doit etre faite après l'élément courant, au lieu de la faire avant, ce qui semble plus logique.
Pourquoi ne pourrait-on pas en faire une qui soit similaire a celle de caml, qui me semble tres bien ?

ps: je poste cette question ici car ma question est pour caml et c et a mon avis il est plus facile de trouver un programmeur caml qui connaisse c que le contraire.

Merci pour toute explication.

[LLB]

Voici à quelques détails près une liste comme en Caml :

Code C :

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
21
22
23
24
25
26
27
28
29
#include <stdlib.h>
#include <stdio.h>
 
typedef struct list
{
  int hd;
  struct list *tl;
} list;
 
list * cons(int x, list *l)
{
  list *new = malloc(sizeof (list));
  new->hd = x;
  new->tl = l;
  return new;
}
 
void print(list *l)
{
  for (list *ptr = l; ptr != NULL; ptr = ptr->tl)
    printf("%d\n", ptr->hd);
}
 
int main(void)
{
  list *foo = cons(3, cons(5, NULL));
  print(foo);
  return 0;
}

Pour faire les choses proprement, il faudrait gérer les erreurs d'allocation, ajouter des const, libérer la mémoire, etc. Mais ça correspond au type int list de Caml.

Si tu as encore des questions après avoir lu ce code, n'hésite pas.

[KateA]

h::q ne provoque pas une copie de q en caml, si?

C'est cette implémentation que je cherche à comprendre : http://nicolasj.developpez.com/articles/listesimple/
Pourquoi ne pas faire l'insertion avant l'élément en cours ?

[Cacophrene]

Bonsoir,

h::q ne provoque pas une copie de q en caml, si?

Un exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
# let x = [ref 1; ref 2; ref 3];;
val x : int ref list = [{contents = 1}; {contents = 2}; {contents = 3}]
# let _ :: y = x;;
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
val y : int ref list = [{contents = 2}; {contents = 3}]
# (List.nth y 1) := 0;;
- : unit = ()
# x;;
- : int ref list = [{contents = 1}; {contents = 2}; {contents = 0}]
# y;; 
- : int ref list = [{contents = 2}; {contents = 0}]

Cordialement,
Cacophrène

[KateA]

Je n'ai pas compris la remarque précédente.
Ce que je veux dire, c'est que je trouve list *new = malloc(sizeof (list));
un peu lourd, et peut-être cela peut être évité.

[Cacophrene]

Re,

Attention j'ai édité mon message alors que tu écrivais le tiens.

Cordialement,
Cacophrène

[LLB]

Ce que je veux dire, c'est que je trouve list *new = malloc(sizeof (list));
un peu lourd, et peut-être cela peut être évité.

Tu es obligé d'allouer chaque noeud de la liste.

h::q ne provoque pas une copie de q en caml, si?

Non, on ne recopie pas q. Mon code ne le recopie pas non plus (ou seulement le pointeur).
Mon code recopie seulement h, mais h est léger : ça peut être un entier, un caractère ou au pire un pointeur vers des données plus grosses.

[KateA]

Mais alors pourquoi dans l'implémentation que j'ai citée pourquoi l'auteur se prend la tête à insérer après l'élément courant, au lieu de faire comme sur caml, ce qui est je trouve plus facile à utiliser ?

[LLB]

En Caml, la liste est utilisée de façon fonctionnelle : une fois créée, elle n'est jamais modifiée. Ajouter un élément renvoie une nouvelle liste (qui partage 99% des données).

Dans l'exemple, la liste est plus impérative. On peut insérer un élément n'importe où, pas seulement en tête, ce qui modifie la liste. On peut aussi supprimer un élément et faire un peu ce qu'on veut. Pour que ça marche, on suppose que les noeuds ne sont pas partagés entre plusieurs listes.

Ce sont deux utilisations très différentes de la liste. Le problème de la version Caml est de savoir quand libérer la mémoire, car on ne sait pas ce qui est partagé. Caml s'en sort avec un garbage collector, ce qui complexifie un peu les choses.

[KateA]

Les notions développées dans le dernier post semblent très intéressantes.
Est-ce que vous pouvez les développer s'il vous plait ?

[LLB]

Pour le garbage collector et la gestion automatique de la mémoire, tu trouveras facilement des articles pour t'expliquer tout ce que tu veux savoir.

Pour l'utilisation impérative de la liste, je te propose un exercice : en C, écris une file en utilisant une liste simplement chaînée. Si tu veux faire la même chose en Caml (c'est aussi un exercice intéressant), il te faudra recopier ta liste de temps à autre. Ce n'est pas le cas en C.

[KateA]

D'accord, mais est-ce que vous pouvez expliquer plus en détail le fonctionnement interne dans les deux cas, et ce qui les différencie ?
Par exemple, avec l'implémentation proposée en C, il n'est pas possible d'implémenter une fonction qui copie n'importe quelle liste, si ?

[KateA]

Bon, peut-être cette question aura plus de succès :
ou est-ce que je peux trouver l'implémentation des listes de caml (ou caml light) (quel dossier, fichier, ligne...) ?
J'ai trouvé les fonctions de base (hd, tl, list_length, ...) mais pas l'implémentation de la liste elle-même.

[gasche]

Le type des listes en Caml, qui sert à coder toutes les fonctions du module List, est le suivant :

Code :

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

1
2
3
type 'a list =
  | []
  | :: of 'a * 'a list

Il est un peu particulier pour deux raisons :
1) il utilise des caractères qui ne sont pas autorisés habituellement dans les types algébriques caml
2) il est défini en tant que primitive par le compilateur

Pour le point 1), cela veut dire que tu ne peux pas à priori déclarer des types algébriques avec des symboles toi-même (même si en pratique le compilateur l'accepte parfois). Tu peux par contre déclarer le type équivalent, et travailler dessus exactement pareil :

Code :

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

1
2
3
type 'a my_list =
  | Nil
  | Cons of 'a * 'a my_list

Pour le point 2), ça veut dire que tu ne trouveras pas cette définition dans une bibliothèque OCaml, mais dans les données de l'environnement primitif du typeur. Dans les sources du compilo OCaml, dans typing/predef.ml, on trouve en différents endroits les bouts de code suivants :

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
and ident_list = Ident.create "list"
(* .. *)
and path_list = Pident ident_list
(* .. *)
and type_list t = newgenty (Tconstr(path_list, [t], ref Mnil))
(* .. *)
  and decl_list =
    let tvar = newgenvar() in
    {type_params = [tvar];
     type_arity = 1;
     type_kind =
       Type_variant(["[]", []; "::", [tvar; type_list tvar]]);
     type_private = Public;
     type_manifest = None;
     type_variance = [true, false, false]}

Le format de définition des primitives est sans intérêt ici, puisqu'il est spécifique à l'implémentation du compilateur, mais le message est clair (ligne "Type_variant(...)"): c'est un type somme à deux cas, "[]" (sans paramètre), et "::" (deux paramètres, 'a et 'a list).

[KateA]

D'accord, merci.
Cela ne m'aide pourtant pas pour mon problème sous jacent, qui serait de savoir comment est implémenté une liste en caml, afin de s'en inspirer pour en faire une en C. Ou alors ce serait trop compliqué ?

J'aimerais utiliser les mêmes idées pour savoir comment ajouter/supprimer un élément en C.

[gasche]

Mon deuxième code était la réponse à ta question. Voilà comment sont implémentées les listes en Caml :

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
21
22
type 'a liste =
  | Vide
  | Cellule of 'a * 'a liste
 
let tete = function
  | Vide -> failwith "la liste est vide"
  | Cellule (t, q) -> t
 
let queue = function
  | Vide -> failwith "la liste est vide"
  | Cellule (t, q) -> q
 
let rec taille = function
  | Vide -> 0
  | Cellule (_, q) -> 1 + taille q
 
let rec filtre condition = function
  | Vide -> Vide
  | Cellule (t, q) ->
      if condition t
      then Cellule (t, filtre condition q)
      else filtre condition q

Une autre façon de coder "taille" :

Code :

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

1
2
3
4
5
let taille liste =
  let rec calcule taille_courante = function
    | Vide -> taille_courante
    | Cellule (_, q) -> calcule (taille_courante + 1) q in
  calcule 0

[KateA]

Ah ok désolé... J'ai un peu de mal à comprendre car je ne vois pas comment faire la même chose en C ??

Prenons par exemple le code suivant :

Code :

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

1
2
3
4
5
6
7
8
9
10
let l1 = [1;2;3]
in
let rec enleve_deux = function
	|[]->[]
	|a::q-> if a = 2 then (enleve_deux q) else a::(enleve_deux q)
in
let l2 = enleve_deux l1
in
(l1,l2);;
- : int list * int list = [1; 2; 3], [1; 3]

Si je fais ça en C en utilisant l'implémentation du post2, je vais obtenir deux fois la même liste (il n'y a pas de 'copie')...

[gasche]

L'idée, c'est qu'en Caml tu n'as pas d'insertion en profondeur dans la liste. Tu n'as en fait pas d'insertion tout court : tu construits des nouvelles listes à partir de listes existantes, sans modifier les listes de départ.

L'algorithme que tu décris est un algorithme récursif. Tu peux l'écrire à l'identique en C, ça donnera quelque chose comme (code pas testé) :

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
list *enleve_deux(list *li)
{
  if (li == NULL) /* liste vide */
    return NULL;
  else {
    if (li->data == 2)
      return enleve_deux(li->next);
    else
      return ajoute(2, enleve_deux(li->next));
  }
}

J'utilise seulement une opération "ajoute" qui construit une nouvelle liste en ajoutant un élément, sans modifier la liste de départ. Voici un exemple de code pour ajoute, pas testé et sans prendre en compte (void *) et compagnie :

Code :

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

1
2
3
4
5
6
7
8
list *ajoute(int tete, list *queue)
{
  list *li = malloc(sizeof(list *));
  if (li == NULL) return NULL;
  li->data = tete;
  li->next = queue;
  return li;
}

Cette méthode marche parfaitement (quand on sait coder en C, ce qui n'est pas mon cas), mais ce n'est pas la manière "habituelle" de faire en langage C : les programmeurs sont plus habitués aux algorithmes impératifs, où on parcourt la liste en supprimant directement les éléments. Ça évite d'allouer de nouvelles cellules à chaque fois (ce qui peut être utile si l'implémentation de la gestion mémoire n'est pas aussi efficace que celle de Caml), mais ça a l'inconvénient que si on voulait conserver la liste de départ.. elle a disparu.