Discussion :

[na$DaL]

Bonjour, je suis en L1MI et je commence la programmation en Scheme, et je bute sur cet exercice qui porte sur le thème de la récursivité sur les listes.

Spécifier et écrire une fonction construire qui, étant donné une liste, retourne l'expression premettant de la construire en utilisant uniquement cons, les éléments atomiques et la liste vide.
Exemple:

Code :

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

1
2
3
4
5
>(construire '(a b))
(cons a (cons b '()))

>(construire '((a b) c))
(cons (cons a (cons b ())) (cons ()))

Mon ébauche:

Code :

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

1
2
3
4
5
6
7
(define construire
  (lambda (l)
    (if (= (lenght l) 1)
        (car (cons '(cons (car l) ()) ()))
         .
         .
         .

Mais le probléme c'est que (car l) n'est pas exécuté et sa me donne quelque chose du genre:

(cons (car l) ())
quand c'est exécuté pour une liste composé d'un seul élément.

Si vous avez une piste??

[Trap D]

Il faut que tu utilises la récursivité sans t'occuper de la longueur de la chaîne
Tu as trois cas

• la liste est vide
• le premier élément de la liste est lui-même une liste
• le premier élément est un atome.

[Gnux]

Salut
La récursivité ça s'apprend (durement!). En fait il te faut un cas de base ( ici tu utilises length) et le cas général (qui par définition est différent du cas de base).
En général tu utilises une structure conditionnelle pour borner ta récursion. Tu as donc la structure classique du if:

Code :

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

(if <cond> <consequence> <alternant>)

Il est essentiel de bien la comprendre pour éviter par exemple d'inverser alternant et conséquent () ou pire encore mélanger les deux...
Ici si l'on définit ton problème, on t'offre une liste citée d'un certain nombre d'éléments d'un certain type citée et ça doit rendre une liste avec les cons apparents.
Le raisonnement est simple: si tu as bien une liste en entrée, il te faut mettre un cons devant son car, puis un autre devant le car du reste de la liste et ainsi de suite.
Cela amène un schéma récursif classique:
(define (ma_jolie_fonction L) ;; L comme Liste
(if (pair? L)
(combinaison (car L)
(ma_jolie_fonction (cdr L)))
0)) ;; ne jamais oublier le cas de base sinon ça foire!
Donc ça devrait donner un code (non-testé!!)du genre:

Code :

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

1
2
3
4
5
(define (construire L)
  (if (pair? L)
   (append(list 'cons (car L) ''())
          (construire (cdr L)))
  0))

Tu devrais réfléchir à ce que tu as en entrée, ce que tu veux en sortie et la façon d'interagir avec les données en entrée pour obtenir la sortie voulue

[Trap D]

Tu n'en n'étais pas loins !

Code :

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

1
2
3
4
5
(define (construire L)
  (if (pair? L)
   (cons 'cons (cons (construire (car L)) (cons (construire (cdr L)) '()))) 
   L))

[Gnux]

Tu n'en n'étais pas loins !

Code :

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

1
2
3
4
5
(define (construire L)
  (if (pair? L)
   (cons 'cons (cons (construire (car L)) (cons (construire (cdr L)) '()))) 
   L))

Ce code est effectivement plus intéressant pour le simple fait qu'il utilise cons dont l'usage est sans aucun doute plus judicieux ici que append + list.
Donc en effet au niveau efficacité et concision c'est nettement mieux. L'alternative aussi. Par défaut je mets toujours 0, cela me permet de vérifier les erreurs (qud je vois 0 a mon prompt, je sais que y'a erreur dans mon traitement).
Enfin le but ici n'était pas de donner la meilleure solution mais simplement de retracer le raisonnement qui doit être fait pour résoudre un problème via un langage de programmation, le reste, c'est de la syntaxe: il "suffit" de lire les bons livres pour s'en sortir alors que ça n'est pas dans les livres que l'on apprend à résoudre des problèmes, c'est en s'y confrontant et en étant capable d'une part de comprdre le raisonnement et ensuite de le reproduire.
En tout les cas, merci pour les corrections