Discussion :

[Phantom_Lord21]

Bonjour!

J'ai une question concernant la manipulation des listes et des enregistrements avec Caml (programmation fonctionnelle). Plus particulièrement dans un cas comme celui-ci:

personnes =
{quartier = 2; secteur= 21;
liste_personnes =
[{nom = "Jean"; numero = 10}; {nom = "Phil"; numero = 5};
{nom = "Marc"; numero = 12}; {nom = "Pierre"; numero = 7}]}

J'ai un enregistrement qui contient 2 "int" et une liste d'enregistrement qui elle-même contient un type string et un autre int.

Comment puis-je faire, à l'aide de fonction récursive, pour:
- "imprimer" (print_string) les noms des personnes une à la suite des autres
- additionner le total des numéros (ici ça donnerait 34 --> 10+12+5+7)

Je ne peux prendre pour acquis qu'il y a nécessairement 4 personnes en tout temps dans la liste_personnes évidemment...

Désolé si c'est vraiment simple mais faut bien commencer à quelque part et là je frappe un os

Merci à l'avance

[ManusDei]

Facile

Code :

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

1
2
3
4
5
6
7
8
9
 
let fun lis ->
let rec aux = fun liste somme -> 
 match liste with [] -> somme
                   |((nom,valeur)::r) -> begin
                                                print_string nom;
                                                aux r somme+valeur;
                                                end
in aux lis 0

Je ne suis pas tout à fait sûr de la syntaxe, mais en gros c'est ça.
La fonction devrait afficher les noms, et te renvoyer la somme.
Elle est récursive, et devrait fonctionner pour toute taille de liste.

Par contre je ne sais plus gérer les enregistrements, donc là je te l'ai fait pour une liste de (string * int ).

[Cacophrene]

Bonjour,

Il suffit d'utiliser un itérateur de type List.fold_left, comme ceci :

Code :

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

1
2
3
4
5
6
let afficher_compter personnes =
  List.fold_left (fun x {nom = str; numero = y} ->
    print_string str;
    x + y
  ) 0 personnes.liste_personnes

Attention : de manière générale il peut être bon de se demander pourquoi on fait des effets de bord dans un itérateur. Je ne sais bien évidemment pas quel est le contexte mais parfois c'est une question fondée.

Cordialement,
Cacophrène

[dest]

Désolé, je me permets de faire un petit hors-sujet mais uniquement parce que la réponse a été fournie.

De façon général, est-il plus performant de faire un fold_left ou un fold_right ?

[Cacophrene]

Salut,

De façon général, est-il plus performant de faire un fold_left ou un fold_right ?

Je ne te donne pas la réponse mais le code source du fichier list.ml devrait te donner une piste :

Code :

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

1
2
3
4
5
6
7
8
9
10
let rec fold_left f accu l =
  match l with
    [] -> accu
  | a::l -> fold_left f (f accu a) l

let rec fold_right f l accu =
  match l with
    [] -> accu
  | a::l -> f a (fold_right f l accu)

Cordialement,
Cacophrène

[dest]

Je dirais que c'est fold_left le plus performant mais j'ai des difficultés pour le justifier.
L'empreinte mémoire du fold_right m'a l'air plus élevé car il faut descendre très bas pour atteindre la liste vide et enfin remonter le futur résultat.
Pour le fold_left, on retourne quasiment tout de suite le résultat de la fonction f donc il n'y a pas besoin de descendre trop profondément.

[Cacophrene]

Bonjour,

fold_left est tailrec, fold_right non. Donc, non seulement fold_left sera globalement plus efficace, mais fold_right échouera sur de grandes listes.

Cordialement,
Cacophrène

[dest]

Bonjour,

fold_left est tailrec, fold_right non. Donc, non seulement fold_left sera globalement plus efficace, mais fold_right échouera sur de grandes listes.

Cordialement,
Cacophrène

Je dois avoir quelques fold_right en stock à modifier par des fold_left

Merci.

[gasche]

Souvent, List.fold_right est plus naturelle à utiliser (c'est le "fold" canonique sur les listes); dans ce cas, je préfère l'utiliser, quitte à modifier sa définition pour limiter son utilisation de la pile si le besoin s'en fait sentir. Par contre, j'utilise toujours fold_left quand ça n'enlaidit pas le code.