Discussion :

[endreillie]

Bonjour,

Je rencontre quelques problèmes quand j'essaie d'ajouter des éléments à des listes.

1) Un participant m'a dit hier qu'augmenter une liste par la méthode element::liste était mieux que par l'opérateur [element] @ liste. Il m'a dit précisément de regarder mon cours parce que cela devrait y être expliqué, mais rien n'y était ! (Notre cours de programmation fonctionnelle de première année est pour le moins laconique, ou du moins ne se penche aucunement sur la théorie, ce qui est pourtant un aspect passionnant de la programmation fonctionnelle.) Pourriez-vous éclairer ma lanterne ?

2) Je souhaite faire un petit bout de programme qui ajoute des éléments à une liste dans l'ordre naturel, c'est à dire de gauche à droite. Par exemple, quand on tape 3 puis 2 puis 1, la liste obtenue est [3; 2; 1]. J'ai essayé les trois méthodes possibles (que je connais du moins) :

a)

Code :

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

1
2
3
let rec ajoute_liste list =
  let element = read_int() in
    (ajoute_liste element::list)

qui évidemment, à l'entrée de 1, 2, 3 donne la liste [3;2;1] (je n'ai pas marqué ici la condition d'arrêt qui est element < 0)

b)

Code :

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

1
2
3
let rec ajoute_liste list =
  let element = read_int() in
    (ajoute_liste list @ [element])

qui fait pareil

et

c)

Code :

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

1
2
3
let rec ajoute_liste list =
  let element = read_int() in
    (ajoute_liste [element] @ list)

qui bizarrement fait la même chose.

J'ai évidemment pensé à retourner la liste ainsi obtenue par une permutation ou en passant par une liste auxiliaire, mais n'y a-t-il pas une méthode plus directe et moins barbare ?

Amicalement,
endreillie

[aubanel]

Bonjour,
lorsque tu manipules des listes, il faut avoir conscience de la structure de donnée sous-jacente. Dans le cas d'ocaml, les listes sont des listes simplement chaînées, ce qui veut dire que chaque élément de la liste contient le lien vers le suivant. La liste est donc complètement représenté par le premier élément (qui désigne son suivant et ainsi de suite) ou aucun élément (la liste vide)
On comprend aisément qu'il est facile d'ajouter un élément en tête : on crée un nouvel élément dont le suivant sera le premier de la liste auquel on veut l'ajouter, et qui par conséquent devient le deuxième. Ajouter un élément en queue en revanche est plus coûteux : Il faut parcourir toute la liste, d'élément en élément, afin d'accéder au dernier, et d'y ajouter le nouvel élément. Si on parle en terme de complexité, ajouter en tête se fait en temps constant (noté O(0) ) tandis qu'ajouter en queue se fait en un temps linéaire avec le nombre d'éléments dans la liste (noté O(n) ).

Si on regarde l'opérateur @, qui prend deux liste et les concatène, on comprend qu'il est O(n) avec le nombre d'éléments de la première liste. Donc

Code :

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

let _ = liste @ [element]

est O(n) avec le nombre d'éléments dans la liste.
Si on écrit

Code :

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

 let _ = List.rev (element::liste)

l'ajout se fait en temps constant, mais le List.rev est lui aussi O(n), on est sensiblement en même complexité.
maintenant s'il vaut ajouter m éléments,

Code :

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

 let _ = liste @[e1]@[e2]@...@[em]

est m*O(n), alors que

Code :

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

 let _ = List.rev(e1::e2::...::e3::liste)

reste O(n)

Concernant la différence entre e::l et [e]@l, le deuxième implique la création de la liste [e], puis la concaténation de deux listes (parcours de la première et son effacement en mémoire). Alors que e::l va faire l'ajout sans création de liste intermédiaire.