Extraire chaque nombre dans la liste et reconstruire la liste?

Question

Je dois créer cette fonction flat qui est supposée re-contracter une nouvelle liste de la liste d'entrée (mais ici, la liste d'entrée peut avoir une liste imbriquée à l'intérieur):

ex. plat (A (B (C) D) A) est (ABCDA)

Mon algorithme est le suivant, pas sûr si elle est correcte:

1. Vérifiez si la liste est vide: sinon, allez sur; si oui, fait - retourne la liste vide
2. Si la liste a une longueur de 1, done - retourne la liste
3. Si la liste a une longueur supérieure à 1, que dois-je faire maintenant? (Je peux utiliser car et cdr pour extraire la liste, mais dans les deux cas, comment puis-je faire récursivement extraire la liste à la fin, et je pense utiliser append pour reconstruire la liste après.)

Toute aide/conseil serait appréciée.

Answer 1

L'indice est que, si la liste n'est pas null?, vous ne devriez pas se concentrer sur la longueur de la liste adoptée pour flat, mais au lieu de vérifier si la car de la liste est une liste elle-même ou tout simplement un atome. Si c'est une liste elle-même, vous voulez l'aplatir, ainsi que l'aplatissement du cdr de la liste.

EDIT: Eh bien, pensez à ce qui se passe dans deux cas différents, celui où vous utilisez cons et celui où vous utilisez append:

(append '(a b c) '(d e f)) => (a b c d e f) 

(cons '(a b c) '(d e f)) => '((a b c) d e f) 

Dans le premier cas, vous obtenez une liste dos plat et Dans le second cas, vous ne récupérez pas une liste à plat. Vous pouvez alors essayer

(define (bad-flatten lst) 
    (if ((null? lst) 
     '() 
     (append (car (flatten lst)) (cdr (flatten lst))))) 

mais il ne fonctionnera pas si l'car de lstn'est pas une liste. Vous avez besoin d'un troisième cas, en utilisant cond, comme ceci:

(define (incomplete-flatten lst) 
    (cond ((null? lst) 
     '()) 
     ((list? (car lst)) 
     (append (flatten (car lst)) (flatten (cdr lst)))) 
     (else 
     ;; you need to do something different here. I can 
     ;; think of at least two options. 
     ))) 

Answer 2

peut-être pas la solution la plus optimisée. Probablement vous pouvez l'améliorer encore:

(define (list-flatten lst) 
    (if (not (null? lst)) 
     (let loop ((args lst) (ret (list)) (c null)) 
     (if (not (null? args)) 
      (begin 
      (set! c (car args)) 
      (cond ((list? c) (loop (cdr args) (append ret (list-flatten c)) c)) 
      (else (loop (cdr args) (append ret (list c)) c)))) 
      ret)) 
     #f))