Discussion :

[soft0613]

Bonjour je dois réaliser le produit cartésien de deux ensembles E1 et E2 implémentés par des listes sans répétitions du type (a b f s) dont l'ordre ne compte pas et obtenir un résultat du type :

Code :

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

1
2
3
4
(ens-prod '(a b c) '(1 2))

> ((a 1) (a 2) (b 1) (b 2) (c 1) (c 2))

J'ai fais ceci mais le résultat me donne trop de A-listes et je ne trouve pas comment m'en débarasser

Code :

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

1
2
3
4
5
 
(define (ens-prod A B)
   (map (lambda (x) (map (lambda (y) (list x y)) B)) A))

> (((a 1) (a 2)) ((b 1) (b 2)) ((c 1) (c 2)))

si quelqu'un a une idée...

[gorgonite]

si tu concatènes les listes contenues dans la liste résultat... ça devrait suffire

[Trap D]

Combine la récursivité et le map.

[Garulfo]

Remarque en passant :

Ce genre de TP est plus simple à mettre en œuvre sous Scheme que sous ocaml. Sous ocaml, le typage est un sérieux frein.

[LLB]

En Caml, traduction littérale de l'exemple donné :

Code :

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

1
2
let ens_prod a b =
  List.map (fun x -> List.map (fun y -> [x; y]) a) b

Je ne vois pas de différence, ici.

[Garulfo]

En Caml, traduction littérale de l'exemple donné :

Code :

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

1
2
let ens_prod a b =
  List.map (fun x -> List.map (fun y -> [x; y]) a) b

Je ne vois pas de différence, ici.

Mais si tu implémentais les ensembles tu utiliserais des listes simples, toi ?
Probablement plus des hashset non ?

Et en général dès que tu commences à penser à ton typage, ça complique la vie. Je ne dis pas que c'est infaisable: je l'ai fait pour montrer à mon collègue comment ça pourrait se faire. Sauf qu'en Scheme la solution est plus simple puisqu'il n'y a pas de problème de typage. Si tu ne manipules que des entiers, ce n'est pas génant. Si tu manipules des entiers et des réelles, ça devient fatiguant... si tu veux des ensembles dans tu ne peux définir l'ensemble d'inclusion a priori, les choses se gatent (mélange d'un nombre n de types).

[Jedai]

Mais si tu implémentais les ensembles tu utiliserais des listes simples, toi ?
Probablement plus des hashset non ?

Et en général dès que tu commences à penser à ton typage, ça complique la vie. Je ne dis pas que c'est infaisable: je l'ai fait pour montrer à mon collègue comment ça pourrait se faire. Sauf qu'en Scheme la solution est plus simple puisqu'il n'y a pas de problème de typage. Si tu ne manipules que des entiers, ce n'est pas génant. Si tu manipules des entiers et des réelles, ça devient fatiguant... si tu veux des ensembles dans tu ne peux définir l'ensemble d'inclusion a priori, les choses se gatent (mélange d'un nombre n de types).

Pour des ensembles de petite taille (<~ 500 éléments), l'emploi de liste est envisageable et plutôt efficace (tout dépend de ce que tu en fais).

Pour ce qui est du typage, je ne suis pas d'accord : dès lors que tu manipules une liste d'éléments homogènes, tu n'as pas à y penser grâce au polymorphisme et si tu as une fonction qui assume qu'il s'agit d'une liste d'entier par exemple, tu ne risques pas de lui passer une liste de string par erreur. De ce point de vue, je trouve que les types simplifient plutôt la programmation.
Les listes hétérogènes sont rarement nécessaires et traduisent souvent un problème de conception, note bien que dans un langage comme Haskell, il est possible de créer des listes hétérogènes facilement (si on connait le langage) et même de faire des listes hétérogènes restreintes (où les types autorisés appartiennent à une même typeclass) , qui sont nettement plus utiles.

--
Jedaï

[Garulfo]

Pour des ensembles de petite taille (<~ 500 éléments), l'emploi de liste est envisageable et plutôt efficace (tout dépend de ce que tu en fais).

Pour ce qui est du typage, je ne suis pas d'accord : dès lors que tu manipules une liste d'éléments homogènes, tu n'as pas à y penser grâce au polymorphisme et si tu as une fonction qui assume qu'il s'agit d'une liste d'entier par exemple, tu ne risques pas de lui passer une liste de string par erreur. De ce point de vue, je trouve que les types simplifient plutôt la programmation.
Les listes hétérogènes sont rarement nécessaires et traduisent souvent un problème de conception, note bien que dans un langage comme Haskell, il est possible de créer des listes hétérogènes facilement (si on connait le langage) et même de faire des listes hétérogènes restreintes (où les types autorisés appartiennent à une même typeclass) , qui sont nettement plus utiles.

--
Jedaï

Les listes hétérogènes sont peut être peu utile pour toi, mais il se trouve que pour le projet de tuteur que fait mon collègue, elles sont très importantes puisqu'il ne connait pas le type qui va être implémenté par ceux et celles qui feront une application pour le tuteur. Il faut donc jouer avec les type polymorphe, mais Scheme se montre bien plus souple là-dessus.
Un exemple simple est un logiciel d'aide pour de la théorie naïve des ensembles. Même en utilisant donc des listes, si tu veux prévoir qu'on fasse des produits cartésiens d'ensemble, tu ne sais pas à quel « type » se réfère l'ensemble. J'emploie ici « type » dans le sens Russellien : son ordre.

Et notes bien que je n'ai cité que ocaml et Scheme, et non Haskell puisque je ne sais pas comment cela pourrait être fait en Haskell

Mais bon c'est général, le type limite la souplesse d'utilisation mais offre de belles récompenses en compensation. Ne me fait surtout pas dire que les types sont plus génants qu'utiles.

[alex_pi]

J'avoue que j'aimerai bien un cas concret ou le polymorphisme n'est pas suffisant. Pour moi en Caml, un produit cartésien ferait quelque chose comme

Code :

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

'a set -> 'b set -> ('a * 'b) set

, et ça me parrait parfaitement convenable

[Garulfo]

J'avoue que j'aimerai bien un cas concret ou le polymorphisme n'est pas suffisant. Pour moi en Caml, un produit cartésien ferait quelque chose comme

Code :

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

'a set -> 'b set -> ('a * 'b) set

, et ça me parrait parfaitement convenable

Je n'ai pas dit que ce n'est pas suffisant ni infaisable !
Du moins, je ne vois rien dans mes messages qui indique cela.
J'ai dit que c'est plus simple avec Scheme -_-

Par exemple si tu as un ensemble S

Code :

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

{1, {'a',1}, {"2 + a", {}}}

le typage n'est pas exactement simple à produire.
Tu utilises des ensembles du module set.
Il te faut donc charger les modules.
Si tu demandes à l'utilisateur de rentrer des valeurs au clavier pour les mettre dans un ensemble, en lui offrant un moyen de faire des ensembles comme élément, as-tu une méthode simple pour le faire sans imposer des types ?

Scheme ne se posera pas la question.
ocaml t'impose de le faire.

Encore une fois, ça a des avantages (nombreux) mais ça limite la flexibilité.

[HanLee]

Je n'ai pas dit que ce n'est pas suffisant ni infaisable !
Du moins, je ne vois rien dans mes messages qui indique cela.
J'ai dit que c'est plus simple avec Scheme -_-

Par exemple si tu as un ensemble S

Code :

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

{1, {'a',1}, {"2 + a", {}}}

le typage n'est pas exactement simple à produire.
Tu utilises des ensembles du module set.
Il te faut donc charger les modules.
Si tu demandes à l'utilisateur de rentrer des valeurs au clavier pour les mettre dans un ensemble, en lui offrant un moyen de faire des ensembles comme élément, as-tu une méthode simple pour le faire sans imposer des types ?

Scheme ne se posera pas la question.
ocaml t'impose de le faire.

Encore une fois, ça a des avantages (nombreux) mais ça limite la flexibilité.

Méthode simple mais verbeuse ?

Après, pour les types utilisateurs, il faut pouvoir construire une petite bijection et sa réciproque, pour faire le lien entre le type construit plus haut et le type utilisateur...
Bon, on perd du typage de nom, on perd la différence entre un type registre et un n-uplet... C'est pas grave à priori.

[alex_pi]

Par exemple si tu as un ensemble S

Code :

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

{1, {'a',1}, {"2 + a", {}}}

le typage n'est pas exactement simple à produire.

Ca ne répond pas vraiment à ma question dans le sens où je ne perçois pas dutout l'intéret d'avoir un tel ensemble non typé.
Pour moi un "objet" (en l'occurence cet ensemble) doit être définis de deux façons en même temps :

1. Comment le construire. Ici, c'est raisonnablement facile, il suffit de mettre les éléments dedans les un après les autres
2. Comment l'utiliser. Là ça se complique ! Vu que tu ne sais pas de quel type sont les éléments de ton ensemble, quelle fonction peux tu leur appliquer ? Si tu n'as pas leur type, je ne vois pas comment tu peux récupérer la moindre information relative à ces éléments ou faire quoi que ce soit avec.

Je ne vois pas de situation utile où l'on peut vouloir mettre à la fois dans un ensemble des fonctions, des chaines de caractères et n-uplets d'entiers...

[Garulfo]

[...]
Je ne vois pas de situation utile où l'on peut vouloir mettre à la fois dans un ensemble des fonctions, des chaines de caractères et n-uplets d'entiers...

Un outil avec un tuteur pour apprendre l'utilisation des ensembles en math de manière naif. Mais on s'en fout de l'application, ça pourrait être pour représenter une structure quelconque, un code quelconque ou je ne sais quoi. Que tu ne trouves pas personnellement d'intérêt est une chose, mais qu'un client t'en imposes le besoin en est une autre. Si on te le demande, tu dois bien le faire non ? Ça ne sert à rien de vouloir contourner le problème en disant « ça ne sert à rien. » Peut-être qu'un jour tu tomberas sur une application où ça sera intéressant pour toi. Dans un cas où tu ne connais pas les objets que tu veux mettre dans ta liste, a priori, tu dois avoir qqchose dans l'idée d'une classe Object, ou un langage faiblement typé.