Discussion :

[larchicha]

Bonjour à tous,

Je suis débutant en Ocaml et j'ai encore quelques problèmes de logique (dans ma tête c'est moyennement clair donc pareil dans mon programme...).

Je vais aller droit au but.

Je dois coder une fonction "enum n" qui me retourne une liste telle que

Code :

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

enum n -> [0,1,...,n]

.

J'ai donc fait :

Code :

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

1
2
3
4
let rec enum n = match n with 
  |0 -> [0]
  |_ -> enum (n - 1)@[n]
;;

Après tests, la fonction me renvoie ce que je veux.

Le problème survient lorsque je souhaite réaliser une autre fonction "enum_droite i n " telle que :

Code :

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

enum i n -> [(i,0);(i,1);(i,2);...;(i,n)]

à l'aide de la fonction List.map .

J'ai donc fait :

Code :

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

1
2
3
4
let enum_droite i n = match n with
  |0 -> [(i,0)]           /* si n = 0 alors je renvoie juste [(i,0)] */
  |_ ->  List.map (fun i -> (i,n)) (enum n)     /* sinon List.map qui crée les couples (i,n) appliquée à ma liste [enum n ] */
;;

En testant, je me retrouve à peu près le bon résultat mais je sens bien que je passe à coté de qqchose niveau compréhension.

Aurais je pu me passer du match .. with ? Ou si vous avez des commentaires suceptibles de m'aider...

Merci d'avance

[Cacophrene]

Bonjour,

Ta fonction enum fait effectivement ce que tu veux, mais il est important de savoir qu'elle n'est pas très efficace. En effet, la manière naturelle d'ajouter des éléments dans une liste en Caml se fait par le début, avec l'opérateur cons ::, et non par la fin avec l'opérateur de concaténation @. Par exemple ce code faut aussi ce que tu veux :

Code :

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

1
2
3
4
5
let enum n =
  let rec build i =
    if i > n then []
    else i :: build (i + 1)
  in build 0

Tu peux aussi stocker la liste en cours de création à chaque appel (accumulation) afin d'éviter d'encombrer la pile d'appels lorsque n est grand. Cela nous donne :

Code :

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

1
2
3
4
5
let enum n =
  let rec build accu i =
    if i < 0 then accu
    else build (i :: accu) (i - 1)
  in build [] n

Remarque bien la manière dont on fait l'itération de 0 à n dans les deux fonctions (parties en vert).

Pour la fonction List.map : cette fonction prend tous les éléments de la liste et leur applique la fonction f reçue en entrée. En conséquence, tu peux écrire :

Code :

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

let enum_droite i n = List.map (fun n -> (i, n)) (enum n)

Cordialement,
Cacophrène

[TropMDR]

Bonjour

Il y a plusieurs problème !

Je dois coder une fonction "enum n" qui me retourne une liste telle que

Code :

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

enum n -> [0,1,...,n]

.

J'ai donc fait :

Code :

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

1
2
3
4
let rec enum n = match n with 
  |0 -> [0]
  |_ -> enum (n - 1)@[n]
;;

Effectivement, ça doit "marcher". mais il y a un soucis de taille ! L'oppérateur @ de concaténation de liste est très inefficace. Quand tu fais l1 @ l2, ça parcours tout l1 pour la recopier avec l1 à la fin. Si tu as quelques notion d'algorithmique et de complexité, ça fait que ta fonction enum est quadratique en n au lieu d'être linéaire. Il y a plusieurs solutions pour ce problème. L'un est de créer la liste "à l'envers" puis de la retourner, l'autre est de faire une fonction qui au lieu d'aller en décroissant de n à 0 va en croissant de 0 à n (elle prendra sans doute deux arguments au lieu d'un !)

Le problème survient lorsque je souhaite réaliser une autre fonction "enum_droite i n " telle que :

Code :

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

enum i n -> [(i,0);(i,1);(i,2);...;(i,n)]

à l'aide de la fonction List.map .

Est ce que tu as bien compris ce que fait la fonction List.map ? Son type est assez clair :

Code :

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

val map : ('a -> 'b) -> 'a list -> 'b list

Elle prend une fonction de 'a vers 'b, une liste de 'a et retourne une liste de 'b. Le seul comportement "raisonnable" qu'on peut attendre de map f l est donc de créer une nouvelle liste qui contient les résultat de l'application de f à chaque élément de l.

Maintenant sachant qu'avec enum, tu es capable de créer la liste
[1; 2; 3; 4], comment utiliser List.map pour créer [(42, 1); (42, 2); (42, 3); (42, 4)] ? Il n'y a pas de récursion à faire, ni de pattern matching.

[EDIT] et si tu n'arrives pas à trouver par toi même, tu peux toujours récupérer les solutions envoyées directement au message précédent :-\[/EDIT]

[larchicha]

Vous êtes au taquet vous 2 (ainsi que blue et LLB...) enfin bref...

Dans ma tête, la fonction map prend une fonction et une liste puis applique cette même fonction à ma liste.

ici je fais : let enum_right = List.map (fonction qui crée un couple (i,n) avec i fixé et n qui croît de 0 à n ) (enum n)

Sauf que dans ma fonction, je ne peux pas appeller "enum" vu que c'est censé me retourner une liste... or je veux seulement les éléments de cete liste... (je m'embrouille tout seul...)

Merci de vos réponses (à tous les 2).

PS : Plus que les réponses, j'aimerais vraiment comprendre le pourquoi du comment... donc si vous aviez l'amabilité d'argumenter avec des exemples (merci) ^^

Edit : Je pense avoir trouver comment fixer i :

Code :

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

let enum_right i n = List.map (fun n -> (i,n)) (enum n) ;;

en m'aidant de la fonction enum sans accumulation donnée par Cacophrène...

Edit 2 : lol que je suis c**, j'avais pas vu que tu m'avais donné exactement la même fonction Caco... j'ai honte -_-.

[larchicha]

Je veux pas abuser de votre temps, mais je bloque...

Déjà, avant de rédiger vos programmes, vous avez un brouillon sous la main ?
(parce que moi oui et ça m'aide à voir le problème sans pour autant m'aider à le résoudre...)

Sinon, je veux cette fois ci, "enum_paires n p" qui me retourne une liste de couple telle que :

enum_paires 1 2 -> [(0,0);(0,1);(0,2);(1,0);(1,1);(1,2)]

soit la multiplication de {0,....,n} et de {0,...,p} sous forme de liste de couple...

J'ai essayé de coder tout ça, mais je bloque sur List.map , non pas sur la fonction (quoique c'est surement faux), mais sur la liste auquelle j'appliquerais la dite fonction...

Code :

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

let enum_paires n p = List.map (fun (enum_right n p) (enum_right p n) -> (n,p)) list ?

Merci d'avance.

[TropMDR]

Dans ma tête, la fonction map prend une fonction et une liste puis applique cette même fonction à ma liste.

Elle applique la fonction à tous les éléments de la liste et retourne la liste des résultats. Ce qui la diffère de List.iter, qui applique la fonction et jète les résultats.

Sauf que dans ma fonction, je ne peux pas appeller "enum" vu que c'est censé me retourner une liste... or je veux seulement les éléments de cete liste... (je m'embrouille tout seul...)

Là j'avoue, je ne comprends rien...
Vu qu'un petit bout de code vaut mieux qu'un long discours:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
        Objective Caml version 3.12.0
 
# (* on definit une liste d'entiers *)
  let l = [1;2;3];;
val l : int list = [1; 2; 3]
 
# (*on applique la fonction carree aux element de l *)
  let l2 = List.map (fun x -> x * x) l;;
val l2 : int list = [1; 4; 9]
 
# (* on peut verifier que l n'a pas ete modifiee *)
  l;;
- : int list = [1; 2; 3]
#

On voit que List.map retourne bien une nouvelle liste. D'ailleurs, pour être bien sûr :

Code :

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

1
2
3
# (* la liste resultat peut etre d'un autre type*)
  List.map (fun x -> "l'entier " ^ (string_of_int x)) l;;
- : string list = ["l'entier 1"; "l'entier 2"; "l'entier 3"]

Edit : Je pense avoir trouver comment fixer i :

Code :

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

let enum_right i n = List.map (fun n -> (i,n)) (enum n) ;;

en m'aidant de la fonction enum sans accumulation donnée par Cacophrène...

Le code de la fonction enum n'a aucun impact sur la définition de enum_right. Tant qu'enum retourne le bon résultat (c'est à dire la liste des entiers de 0 à n), ton code est correct.

Sinon, pour éviter les confusions, il est déconseillé de "masquer" une variable existante (ce conseille a *évidement* de nombre contre-exemples). J'aurais donc plus écris quelque chose comme

Code :

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

let enum_right i n = List.map (fun x -> (i,x)) (enum n) ;;

[TropMDR]

Déjà, avant de rédiger vos programmes, vous avez un brouillon sous la main ?
(parce que moi oui et ça m'aide à voir le problème sans pour autant m'aider à le résoudre...)

Disons que ça dépend de la difficulté du programme Pour écrire enum, soyons honnête, non. Pour mes projets de recherche, oooooh que oui !

Sinon, je veux cette fois ci, "enum_paires n p" qui me retourne une liste de couple telle que :

enum_paires 1 2 -> [(0,0);(0,1);(0,2);(1,0);(1,1);(1,2)]

Si tu as le droit d'utiliser la librairie standard, regardehttp://caml.inria.fr/pub/docs/manual...html#VALconcat. Avec enum, enum_droit et List.map, tu n'as besoin de rien d'autre.
Je te laisse chercher un peu

[larchicha]

Merci de cette réponse, j'en prend bonne note... *clarification de List.map : check*

[larchicha]

Pourriez vous m'indiquer la syntaxe de List.concat s'il vous plaît ?

j'ai beau essayer List.concat l1 l2 ou l1.concat l2... et puis il n'y a pas d'exemple sur caml.inria.fr :s

Merci d'avance...

Edit : Merci Cacophrène

[Cacophrene]

Bonsoir,

Pourriez vous m'indiquer la syntaxe de List.concat s'il vous plaît ?

j'ai beau essayer List.concat l1 l2 ou l1.concat l2... et puis il n'y a pas d'exemple sur caml.inria.fr :s

Regarde la signature de la fonction : val List.concat : 'a list list -> 'a list. Cela veut dire que la fonction reçoit une liste de listes en entrée... souvent la signature à elle seule est une bonne documentation.

Cordialement,
Cacophrène

[larchicha]

Bon je me lance, mais je bloque toujours... non pas que je ne sache pas quoi faire, j'ai compris le principe mais je sens que même si j'ai le résultat voulu, c'est pas très clair...

Code :

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

let enum_paires n p = List.map (fun x -> List.concat [(enum_right x n)]) (enum p);;

List.map -> j'applique la fonction enum_right de façon à obtenir mes paires -> sur ma liste (enum p)
- j'aurais préféré concaténer enum p et enum n et appliquer ma function dessus mais je me suis dis que vu que p > n (dans ce cas ci) , ça ferait l'affaire... -

Merci d'avance pour vos réponses.

[TropMDR]

Encore mieux que dvp.net, il y a... ocaml !

Code :

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

1
2
let enum_paires n p = List.map (fun x -> List.concat [(enum_right x n)]) (enum p);;
val enum_paires : int -> int -> (int * int) list list = <fun>

ça retourne une (int * int) list list. Et tu attends une (int * intà list. Mmmmh. Qu'est ce qui pourrait faire passer de l'un à l'autre ?

[larchicha]

Justement le List.concat ... mais je l'ai déja mis dans la fonction ²²

Je prends le temps de chercher... sinon merci pour le "pas à pas"

Edit : Peut être que :

Code :

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

let enum_paires n p = List.concat (List.map (fun x -> List.concat [(enum_right x n)]) (enum p));;

Oh yeah ?

[TropMDR]

Code :

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

let enum_paires n p = List.concat (List.map (fun x -> enum_right x n) (enum p));;

devrait être encore mieux. Essaye de bien comprendre pourquoi le List.concat du milieu ne servait à rien du tout, et vérifie que tu comprends *vraiment* pourquoi ça marche

[larchicha]

Merci à vous, tout est bien plus clair ...

PS : Vu la qualité de tes réponses TropMDR, tu mérites plus de points sur ce forum ^^