Discussion :

[passio]

Bonjour, je dois charger un dictionnaire de 300.000 mots, seulement j'explose la pile... Stack overflow during evaluation (looping recursion?).
J'ai bien vu quelques sujets qui parlent de la récursivité terminale, etc... mais pas de réelle solution.

Voilà ma fonction :

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
let rec lire = function (ii) ->
 
        try
 
          let i = input_line (ii) in
 
            i :: lire (ii)
 
        with End_of_file -> [];;
 
let charge = function (st) ->
 
        let ii = open_in st in
 
          lire (ii);;

Quelqu'un a t-il une solution pour que je puisse charger tout mon fichier ?

Merci

[gorgonite]

récursivité terminale...

[passio]

Oui, sauf que j'ai déjà eu bien du mal à faire cette fonction, j'ai pompé la moitié... J'ai fait 3 séances de caml donc, je suis pas contre un meilleur coup de pouce.

[prgasp77]

Pour faire court*, le principe de la récursivité terminale (qui est indépendante de la syntaxe OCaml) est de transmettre aux sous-appels le résultat partiel construit jusque là ; chaque itération (appel de la fonciton récursive) transforme ou complète le résultat partiel, jusqu'à parfaire la condition d'arrêt ; il n'y a plus qu'à retourner le résultat tout prêt.

Un exemple t'aidera à mieux comprendre. Tu trouveras l'exemple du calcul de la factorielle en rec term un peu partout sur le web ; en voici un autre : la somme de tous les éléments d'une liste (dans un cas réel, préférer l'usage de List.fold_left (+) 0) :

Code :

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

1
2
3
4
5
6
7
8
9
10
let sum_list_elements l =
   let rec aux acc = function
   | [] -> acc
   | head :: tail -> aux (acc + head) tail
   in
   aux 0 l
;;
val sum_list_elements : int list -> int = <fun>
# sum_list_elements [0;1;2;3;4;5;6;7;8;9;10] ;;
- : int = 55

Explicaitons
Comme tu le vois, dans sum_list_elements (qui n'est pas récursive, inutile), on crée une fonction auxiliaire qui elle fait le travail ; mais elle demande un argument supplémentaire (on verra après pourquoi) qui est zéro ; plutôt que de donner à l'utilisateur cette fonction à l'usage particulier, on l'encapsule dans une fonction bien plus claire (qui est sum_list_elements et qui prend tout simplement en argument une liste d'entiers).

La fonction aux prend donc deux arguments. Le second est une liste d'entiers à sommer. Le premier, appelé accumulateur (et ça prend tout son sens ici ) est la somme de tous les éléments de la liste déjà traités.

Voici ce que fait la fonction aux :

• si on lui donne une liste d'entiers non vide, elle extrait le premier élément, l'ajoute à l'accumulateur et s'appelle elle-même en fournissant l'accumulateur modifié et la queue de la liste ;
• si on lui donne une liste vide, elle retourne simplement l'accumulateur, qui contient déjà la somme de tous les entiers traités, soit ceux de la liste.

Exemple pour aux 0 [1;2;3]

Code :

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

1
2
3
4
5
aux 0 [1;2;3]
aux (0+1 → 1) [2;3]
aux (1+2 → 3) [3]
aux (3+3 → 6) []
6

L'intérêt de la récursivité terminale, maintenant que tu as compris son principe, c'est de permettre à OCaml d'optimiser l'appel de la fonction. Dans un cas de récursivité non terminale, une fois arrivés à la condition d'arrêt, les appels successifs retournent leur résultat à l'appel père ; ce résultat est traité puis remonte au grand-père, à l'arrière grand-père… jusqu'à remonter à l'appel premier. Ainsi, OCaml est obligé de garder une trace de tous les appels et de leurs arguments qui sont empilés en mémoire (je te dis pas la duplication de mémoire que ça implique).
Avec de la rec term, l'appel père n'a pas besoin de traiter le résultat du fils, car le fils a en main toutes les informations nécessaires (la somme des éléments précédents et la liste des éléments suivant dans notre cas). OCaml peut donc « oublier » les appels parents et libérer la pile.

J'espère que j'ai été clair, désolé pour le long message, je suis en forme aujourd'hui.

Edit
(*) HAHA !

[passio]

Salut prgasp77,
avant tout je te remercie pour ta réponse et le temps que tu as consacré à m'expliquer.

Effectivement, avant même d'entendre parler de récursivité terminale, j'avais bien eu l'intuition de procéder ainsi, c'est à dire découper la tache en repassant la liste déjà créée à chaque nouvel appel de fonction jusqu'à avoir lu tout le fichier...

Algorithmiquement parlant, ça ne me pose aucun problème, enfin je vois la chose ainsi :

Lis mon fichier, après N lignes lues, rappelle la fonction et passe lui en argument la liste déjà crée à laquelle tu ajoutes (: la fonction récursives de lectures, etc... Seulement, c'est la syntaxe ici qui me pose problème, parce qu'il y a des try/with...

Je vais essayer de modifier ma fonction en prenant ton exemple en modèle. C'est très frustrant car je comprends très simplement la manière dont tu expliques la chose mais quand je jette un oeil au code, ça coule pas du tout comme de l'eau de source à certains endroit... Et quand j'essaye du coup de faire pour lire un fichier, ça complexifie davantage et m'égare... J'essaye...

edit :
Après 40 minutes :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
let rec lire file =
        try
        			   let rec aux acc = function
               | _ -> let mot = input_line (file) in
         			 acc :: aux (mot::acc) file 
         			 in 
         			 aux [] file
         with End_of_file -> [];;
 
let charge = function (st) ->
        let ii = open_in st in
          lire (ii);;

# let charge = function (st) ->
val charge : string -> 'a list list = <fun>
# let rec lire file =
val lire : in_channel -> string list list = <fun>


ça me renvoie une liste de liste... Je n'vois pas quoi faire d'autre... J'ai tenté pleins de choses mais rien ne fonctionne...



Edit :
Après 50 minutes :
J'aurai bien tenté :

Code :

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

1
2
3
4
5
6
7
8
let rec lire file =
        try
        			   let rec aux acc = function
               | _ -> let mot = input_line (file) in
         			 aux (mot::acc) file 
         			 in 
         			 aux [] file
         with  | End_of_file -> acc;;

mais je ne peux pas renvoyer acc dans le with... Merci de bien vouloir m'aider encore un peu...

Edit : Après plus d'une heure :

C'est impossible... -_- Quelqu'un me donne une solution en itératif, je n'ai pas appris l'itératif avec ocaml et j'aimerai m'en préserver car on nous l'a interdit en cours...

Après 1h30 :

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
let rec lire file =
  try
    let rec aux acc x = function
 
        | _ ->
            if x = 10000 then acc @ lire file
            else
              let mot = input_line (file) in
                aux (mot :: acc) (x + 1) file
    in
      aux [] 0 file
  with | End_of_file -> [];;
 
let charge = function (st) ->
        let ii = open_in st in
          lire (ii);;

ça marche ^^...

[gorgonite]

Tu ne fais pas vraiment de la récursivité terminale, tu te contentes juste "d'en faire un peu"

Par ailleurs, il faudrait ne pas inverser l'ordre de la liste...

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
let lire file =
  let rec aux acc = 
     try
        let mot = input_line file in
        aux (mot::acc)
     with |End_of_file -> acc
  in
  List.rev (aux [])
;;
 
let charge st =
   let ii = open_in st in
   lire ii
;;
 
List.iter (fun s -> Printf.printf "%s\n" s) (charge "toto.txt");;