Discussion :

[abssef]

Bonjour,
je suis débutant en langage LISP, j'ai essayé en vain de parvenir à une solution d'un exercice, et je cherche une âme charitable pour m'aider, voila l'énoncé de l'exercice

"Définir le but aplatir( L,L1 ),qui prend une liste L quelconque , avec éventuellement des listes imbriquées , et retourne dans L1 la liste aplatie ( sans imbrication des listes).

merci d'avance

[rutabagas]

Bonjour,
je suis débutant en langage LISP, j'ai essayé en vain de parvenir à une solution d'un exercice, et je cherche une âme charitable pour m'aider, voila l'énoncé de l'exercice

"Définir le but aplatir( L,L1 ),qui prend une liste L quelconque , avec éventuellement des listes imbriquées , et retourne dans L1 la liste aplatie ( sans imbrication des listes).

merci d'avance

Ben on aurais bien voulu voir tes essais ... mais comme je trouve ton problème intéressant je me suis amusé à faire cela :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
(defun aplati (lst) 
  (if (null lst) 
    'done
    (if (atom (first lst))
      (progn
	(print (first lst))
	(setf lst (cdr lst))
	(aplati lst)
	)
      (progn 
	(setf lst (first lst))
	(aplati lst)))))

ça marche pour une liste du type: (a (b (c d)))
mais pas pour une liste du type : (a (b c) (e f g h))

J'espère que tu finiras le travail tout seul ...

(suis pas un expert Garulfo corrige mois si mon code est pas très pro)

[abssef]

merci bien pour ton aide

[Garulfo]

[...]
suis pas un expert Garulfo corrige mois si mon code est pas très pro

Déjà, ce n'est pas très fonctionnel ! Les setf sont à proscrire. De plus ce n'est pas ce qui est demandé je pense. Tu produis un affichage, l'énoncé parle de retourner une liste.

La question est aussi de savoir le contexte dans lequel s'est demandé. Par exemple, si son prof vient de lui apprendre la programmation par flots (map, fold etc) ce n'est probablement pas l'approche attendue.

Maintenant, avant de répondre à Abseff, est-ce que celui-ci a écrit un algorithme ? Sinon, c'est la première chose à faire...

[rutabagas]

Déjà, ce n'est pas très fonctionnel ! Les setf sont à proscrire. De plus ce n'est pas ce qui est demandé je pense. Tu produis un affichage, l'énoncé parle de retourner une liste.

La question est aussi de savoir le contexte dans lequel s'est demandé. Par exemple, si son prof vient de lui apprendre la programmation par flots (map, fold etc) ce n'est probablement pas l'approche attendue.

Maintenant, avant de répondre à Abseff, est-ce que celui-ci a écrit un algorithme ? Sinon, c'est la première chose à faire...

Merci de tes conseils Garulfo.
J'ai produit un affichage car effectivement il n'a pas donné de code et je ne voulais pas faire tout son boulot. (L1 ne sera pas dans le bon odre)
On ne peut pas tomber dans la méfiance maximum et toujours penser que l'étudiant est un tricheur systématiquement et que les profs sont tous parfaits (Je suis prof dans le secondaire (pas d'info) et je connais la maison ...)
Merci encore pour tes remarques que j'apprécie.

[Sygénème]

Oui, c'est un problème classique des cours de LISP...
Tu dois connaître les notions suivantes :
- les LISTES
comment savoir si on à affaire à une liste ?
comment savoir qu'une liste est vide ?
comment récupérer le premier élément d'une liste ?
comment retirer le premier élément d'une liste ?
comment ajouter un élément a une liste ?
comment concaténer deux listes ?
- les FONCTIONS et la "récursivité"
- comment construire une conditionnelle

Voilà pour les outils...

Maintenant le mieux pour toi est de trouver la solution par toi même mais si tu veux, voici quand même ma solution sur le principe suivant :

> (aplatir '(A (A B) (A B (A C X)) ((A B)(C D)(E F)) B))
(A A B A B (A C X) (A B) (C D) (E F) B)

Je définit une fonction récursive "aplatir" qui prend une liste comme unique paramètre.
Si la liste et vide, "aplatir" retourne une liste vide
Si le premier élément de ma liste et une liste, je le concaténe avec le reste de la liste aplatit.
Sinon j'ajoute ce premier élément comme premier élément du reste de la liste aplatit.

Je ne sait pas si c'est vraiment clair... Je pourrais éventuellement te donner le code en Scheme au besoin...

Maintenant si tu veux un aplatissement total de la liste, je te laisse faire, il ne doit pas manquer grand chose...

[Garulfo]

Maintenant le mieux pour toi est de trouver la solution par toi même mais si tu veux, voici quand même ma solution sur le principe suivant : [...]

Je définit une fonction récursive "aplatir" qui prend une liste comme unique paramètre.
Si la liste et vide, "aplatir" retourne une liste vide
Si le premier élément de ma liste et une liste, je le concaténe avec le reste de la liste aplatit.
Sinon j'ajoute ce premier élément comme premier élément du reste de la liste aplatit.

Il y a une petite faute de sens. Aplatir doit aplatir tout « l'arbre ». Au final, les feuilles de l'arbre sont dans une liste « plate ». Donc avec ton exemple :

Code :

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

1
2
> (aplatir '(A (A B) (A B (A C X)) ((A B)(C D)(E F)) B))
(A A B A B A C X A B C D E F B)

Il ne suffit donc pas de le concaténer.

[Sygénème]

Arf OK ! je m'attaque au problème alors (en scheme cepandant).

EDIT : C'était bien plus simple que je l'imaginai intuitivement, il suffit juste d'aplatir aussi "le premier élément de ma liste qui et une liste" avant de le concaténer...

soit en scheme le code suivant :

Code :

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

1
2
3
4
5
6
 
(define (aplatir L)
  (cond
    ((null? L) ())
    ((pair? (car L)) (append (aplatir (car L)) (aplatir (cdr L))))
    (else (cons (car L) (aplatir (cdr L))))))

[Garulfo]

Et maintenant... dans une forme récursive terminale ??

[Sygénème]

Voilà, j'ai (je pense) réussi ! Ce fut plus compliquer que j'aurais cru et mon ego en à prit un coup ^^

Donc voici ma solution, avec en rouge les passages qui m'ont posé problème :

Code :

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

1
2
3
4
5
6
7
8
(define (aplatir L)
  (define (traitement L X)
    (cond
      ((null? L) X)
      ((pair? (car L)) (traitement (cdr L) (traitement (car L) X)))
      (else (traitement (cdr L) (append X (list (car L)))))))
   (traitement L ()))

[Jedai]

Ta fonction est correcte mais lente, à cause du append elle est en O(n²) au lieu d'être en O(n) comme elle peut l'être :

Code :

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

1
2
3
4
5
6
7
8
9
10
(define (flatten L)
  (define (flatten-rev rest flattened)
    (cond
      ([null? rest] flattened)
      ([pair? (car rest)] 
       (flatten-rev (cdr rest) 
                    (flatten-rev (car rest) flattened)))
      (else 
       (flatten-rev (cdr rest) (cons (car rest) flattened)))))
  (reverse (flatten-rev L ())))

--
Jedaï

[Sygénème]

Effectivement çà marche aussi comme çà !
En fait si tu regarde mon code, les fonctions provoquant le O(n²) sont en rouge ; ma première idée était bien (cons (car L) ... mais étrangement çà transformait la liste (A B C) en liste (().A ().B ().C).
M'est d'avis que j'ai du me tromper dans le parenthèsage...