Racket/Scheme Flatten Explications

Question

Quelqu'un peut-il m'aider à décomposer exactement l'ordre d'exécution des versions suivantes d'aplatissement? J'utilise Racket.

version 1, est à partir de la raquette elle-même, tandis que la version deux est plus commun? la mise en oeuvre.

(define (flatten1 list) 
    (let loop ([l list] [acc null]) 
    (printf "l = ~a acc = ~a\n" l acc) 
    (cond [(null? l) acc] 
      [(pair? l) (loop (car l) (loop (cdr l) acc))] 
      [else (cons l acc)]))) 

(define (flatten2 l) 
    (printf "l = ~a\n" l) 
    (cond [(null? l) null] 
     [(atom? l) (list l)] 
     [else (append (flatten2 (car l)) (flatten2 (cdr l)))])) 

Maintenant, exécutant le premier exemple avec « (1 2 3) produit:

l = (1 2 3) acc =() 
l = (2 3) acc =() 
l = (3) acc =() 
l =() acc =() 
l = 3 acc =() 
l = 2 acc = (3) 
l = 1 acc = (2 3) 
'(1 2 3) 

tandis que le second produit:

l = (1 2 3) 
l = 1 
l = (2 3) 
l = 2 
l = (3) 
l = 3 
l =() 
'(1 2 3) 

L'ordre d'exécution semble différent. Dans le premier exemple, il semble que la seconde boucle (loop (cdr l) acc) tire avant la première boucle puisque '(2 3) est en train d'imprimer tout de suite. Alors que dans le deuxième exemple, 1 s'imprime avant le '(2 3), ce qui semble être le premier appel à aplatir à l'intérieur d'append est évalué en premier.

Je passe par le Little Schemer mais ce sont des exemples plus difficiles sur lesquels je pourrais vraiment utiliser de l'aide.

Merci beaucoup.

Answer 1

La principale différence est la suivante:

• flatten1 œuvres de stocker les éléments de sortie (première à partir du côté cdr, puis depuis le côté car) dans un accumulateur. Cela fonctionne parce que les listes sont construites de droite à gauche, donc travailler d'abord sur le côté cdr est correct.
• flatten2 fonctionne en aplatissant de façon récursive les côtés car et cdr, puis append en les assemblant.

flatten1 est plus rapide, surtout si l'arbre est lourd du côté car: l'utilisation d'un accumulateur signifie qu'il n'y a pas de copie de la liste supplémentaire, peu importe quoi. Alors que l'appel append dans flatten2 provoque la copie du côté gauche du append, ce qui signifie beaucoup de copie de liste supplémentaire si l'arborescence est lourde du côté car. Donc, en résumé, je considérerais flatten2 une mise en œuvre d'aplatissement débutant, et flatten1 une version professionnelle plus polie. Voir aussi my implementation of flatten, qui fonctionne selon les mêmes principes que flatten1, mais en utilisant un pli gauche au lieu du pli droit utilisé par flatten1.

(Une solution de pli gauche utilise moins d'espace de pile mais potentiellement plus d'espace de tas.) Une solution de pli droit utilise plus de pile et moins de tas, bien qu'une lecture rapide de flatten1 suggère dans ce cas que l'utilisation du tas même que ma mise en œuvre.)

Answer 2

Pas vraiment une réponse à votre question (Chris a déjà fourni une excellente réponse!), Mais pour être complet bien voici encore une autre façon de mettre en œuvre flatten, similaire à flatten2 mais un peu plus concis:

(define (atom? x) 
    (and (not (null? x)) 
     (not (pair? x)))) 

(define (flatten lst) 
    (if (atom? lst) 
     (list lst) 
     (apply append (map flatten lst)))) 

Et une autre façon de mettre en œuvre la version gauche fois (avec plus en commun à flatten1), en utilisant les procédures standard de raquette:

(define (flatten lst) 
    (define (loop lst acc) 
    (if (atom? lst) 
     (cons lst acc) 
     (foldl loop acc lst))) 
    (reverse (loop lst '())))