Verwenden von Cons/Auto vs Append zum Erstellen von Listen in Racket

Question

Ich möchte eine Liste von Quadraten machen. Ich kann es mit folgendem Code:

(define (makelistsq n) 
    (define outlist '()) 
    (for ((i n)) 
    (set! outlist (append outlist (list (* i i)))) 
    ) 
    outlist 
) 

(makelistsq 5) 

Ausgang:

'(0 1 4 9 16) 

Aber ich habe gesehen, dass oft Nachteile und Auto Schlüsselwörter verwendet werden, um zu erstellen und zu Listen hinzufügen. Hat diese Methode einen Vorteil gegenüber dem Anhängen wie oben? Also, folgt besser oder gleich wie oben:

(define (makelistsq2 n) 
    (define outlist '()) 
    (for ((i n)) 
    (set! outlist (cons (* i i) outlist)) 
    ) 
    (reverse outlist) 
) 

Vielen Dank für Ihre Antworten/Kommentare.

Edit: auf dieser Seite Cons element to list vs cons list to element in Scheme wird erwähnt, dass alle Verwendung von append falsch ist:

Für den seltenen Gelegenheiten, in denen Sie ein Element am Ende hinzuzufügen (und glauben Sie mir, tun so allgemein bedeutet, dass Sie denken, der Algorithmus falsch) Sie können Append

Answer 1

Ich werde nicht meine eigene Antwort wiederholen: P. Ja, die Verwendung von append ist im Allgemeinen der falsche Weg zum Erstellen einer Ausgabeliste. Aber keine Ihrer Implementierungen scheint richtig - die meiste Zeit, Sie müssen set! und Schleifen vergessen.

Rekursion ist der Weg zu gehen, und mit cons und (falls erforderlich) reverse am Ende ist der bevorzugte Weg, um eine Liste zu erstellen. In der Tat kann die Funktion in der Frage kurz und bündig eingebaute Prozeduren verwendet werden, ausgedrückt, und dies ist der empfohlene Weg, wenn Funktions-Stil Code zu schreiben:

(define (makelistsq2 n) 
    (map (lambda (x) (* x x)) 
     (range n))) 

Aus Gründen der Vollständigkeit, lassen Sie zu sehen ist, wie würden wir Schreiben Sie den Vorgang von Grund auf neu, verwenden Sie cons zum Erstellen der Ausgabe - für die seltenen Fälle, wenn es keine integrierte Prozedur gibt, die das tut, was Sie brauchen. Dies erzeugt einen rekursiven Prozess, feststellen, dass wir hier von Null bis n-1 gehen:

(define (makelistsq2 n) 
    (define (helper i) 
    (if (= i n) 
     '() 
     (cons (* i i) 
       (helper (add1 i))))) 
    (helper 0)) 

Die obige Lösung ist in Ordnung, und funktioniert perfekt für kleine Listen. Wenn (und nur wenn) die Ausgabeliste groß ist, möchten Sie sie vielleicht mit Tail-Rekursion erstellen; Dies ist effizienter, da es nicht für die Iteration zusätzliche Speicher benötigt - wir eine benannten let verwenden werden, und beachten Sie, dass dies einen iterativen Prozess erzeugt, von n-1 auf Null gehen:

(define (makelistsq2 n) 
    (let loop ((i (sub1 n)) (acc '())) 
    (if (negative? i) 
     acc 
     (loop (sub1 i) (cons (* i i) acc))))) 

Egal, welche Implementierung Sie wählen, ist das Ergebnis nun wie erwartet:

(makelistsq2 5) 
=> '(0 1 4 9 16) 

Answer 2

cons der Konstruktor für ein Paar ist. Eine Liste ist nichts anderes als eine Kette von cons, die durch die leere Liste () beendet wird.

append ist eine Funktion, die cons in der Implementierung verwendet.Hier ist die Implementierung für ein zwei Argument append:

(define (append lst1 lst2) 
    (if (null? lst1) 
     lst2 
     (cons (car lst1) 
      (append (cdr lst1) lst2)))) 

In einfachem Englisch macht es ein neues Paar für jedes Paar von lst1 und dann die lst2 befestigen. Es ist nicht sehr effizient, also muss in Ihrem ersten Beispiel, um diese 5-Elemente-Liste zu erstellen, eine 4-, 3- und 2-Element-Liste zusätzlich zu der Liste mit einem Element erstellt werden, die Sie explizit für jeden Schritt erstellt haben.

Beim Arbeiten mit Listen iteriert es in der Reihenfolge vom ersten bis zum letzten, aber die Erstellung einer Liste geschieht von Ende zu Anfang. Oft ist es nicht möglich, etwas in umgekehrter Reihenfolge zu tun und das Ergebnis muss am Ende umgekehrt werden, aber in Ihrem Fall ist es einfach, rückwärts anstatt aufwärts zu zählen.

(define (make-square-list end) 
    (let loop ((n (sub1 end)) (acc '())) 
    (if (< n 0) 
     acc 
     (loop (sub1 n) 
       (cons (* n n) acc))))) 

Mit Funktionen höherer Ordnung können Sie den Textvorschlag beseitigen, sondern #!racket haben eine Alternative, die noch kürzeren Code for/list genannt macht.

(define (make-square-list end) 
    (for/list ((n (range end))) 
    (* n n))) 

for/list ist grundsätzlich die gleiche wie map sondern als eine besondere Form.

Answer 3

meine Version:

#lang racket 

(define (make-square-list n) 
    (let loop ([count 1] 
      [result_list '()]) 
    (if (<= count n) 
     (loop (add1 count) (cons (* count count) result_list)) 
     (reverse result_list)))) 

(make-squqre-list 10) 

(1 4 9 16 25 36 49 64 81 100)