Reverse-Liste in Schema

Ich versuche, eine Liste in Schema zu umkehren und ich kam mit der folgenden Lösung:Reverse-Liste in Schema

(define l (list 1 2 3 4)) 

(define (reverse lista) 
    (car (cons (reverse (cdr (cons 0 lista))) 0))) 

(display (reverse l))

Obwohl es funktioniert verstehe ich nicht wirklich, warum es funktioniert.

In meinem Kopf würde es zu einer Reihe von verschachtelten Nachteile bis Nachteile von() (was die Cdr einer Liste mit einem Element) bewerten.

Ich glaube, ich verstehe das Substitutionsmodell nicht, könnte mir jemand erklären, warum es funktioniert?

Obs:

Es soll nur Listen nicht verschachtelt arbeiten.
In Form von SICP, Übung 2.18.
Ich weiß, dass es viele ähnliche Fragen gibt, aber soweit ich gesehen habe, präsentierte keiner diese Lösung .

Danke

Quelle

2016-07-13 Eduardo Hashimoto

bist du sicher? der Code, den du zeigst, funktioniert offensichtlich nicht, und aus gutem Grund - "(cdr (cons 0 lista))" wird zu "lista" ausgewertet, also endlos. Eine rekursive Definition muss den Basisfall haben und in jedem Schritt darauf testen. Ihre Prozedur hat es nicht, es kommt immer wieder vor. Die einzige Möglichkeit, wie ich diese Sache sehen kann, besteht darin, stattdessen eine eingebaute Reverse hervorzurufen, also hattest du vielleicht einen Tippfehler bei der Definition? – dercz

Danke, ich wusste nicht über die eingebaute Rückseite. Ich verwende es anstelle meiner definierten Prozedur, wenn ich den Namen ändere, funktioniert es wirklich nicht. Entschuldigung für diese Frage. –

Kein Problem! Jeder, den ich kenne, lispelte, machte ähnliche Fehler (mich eingeschlossen). Ich beschloss, die Antwort trotzdem zu schreiben. Viel Glück und happy hacking, ich hoffe, Sie genießen Intrigen! – dercz

Dieses liest so ziemlich das gleiche wie die Lösungen in anderen Sprachen:

, wenn die Liste leer ist, eine leere Liste zurück. Sonst ...
zerhacken das erste Element (CAR)
Umkehren der Rest der Liste (CDR)
append (CONS) das erste Element zu dieser Umkehrung
Rückkehr das Ergebnis

off

Nun ... mein Verständnis von LISP Tagen gegeben, würde der Code wie folgt aussehen:

(append (reverse (cdr lista)) (list (car lista)))

..., die meine Beschreibung passt ab Ove.

Quelle

2016-07-13 17:29:39 Prune

CAR = das Kopfelement greifen; CDR = schnappen Sie sich den Rest der Liste; CONS = anhängen; 0 = NULL. – Prune

Ok, danke. Ich verstehe das, aber was ist mit (define (reverse l) (cons (reverse (cdr l)) 0)). Es gibt kein Auto und es gibt immer noch die umgekehrte Liste zurück (weniger das erste Element). Wenn ich anstelle von 0 (Auto l) hätte, wäre das in Ordnung, was du gesagt hast. Aber ich stelle mir nicht vor, wie es ohne Auto passiert. –

In Wahrheit sehe ich nicht genau, wie Ihr gegebener Code funktioniert; Ich spreche LISP, anstatt Scheme. Von dem, was ich weiß, ** cons (0 x) ** gibt einfach ** x ** zurück, also sagt * meine * Lesung, dass dies in unendliche Rekursion gehen wird. – Prune

[Da dies oft der Fall ist, schreibe ich die Antwort sowieso]

Schema Implementierungen ihre builtin Versionen von Reverse, Karte haben, hängen usw., wie sie in RXRS angegeben sind (z https://www.cs.indiana.edu/scheme-repository/R4RS/r4rs_8.html).

Im Lernschema (und eigentlich jeden Lisp-Dialekt) ist es wirklich wertvoll, sie trotzdem zu implementieren. Die Gefahr besteht darin, dass die eigene Definition mit der eingebauten Kollision kollidieren kann (obwohl z. B. die Definition des Schemas oder das Etikett von Lisp sie beschatten sollte). Daher ist es immer lohnt sich, diese von Hand hergestellt Umsetzung mit einem anderen Namen zu nennen, wie „my-Reverse“, „my-append“ usw. Auf diese Weise können sich viel Verwirrung, wie in der folgenden sparen:

(let ([append 
     (lambda (xs ys) 
      (if (null? xs) 
       ys 
       (cons (car xs) (append (cdr xs) ys))))]) 
(append '(hello) '(there!)))

- dieser scheint zu arbeiten, eine falsche Impression erstellen, die "Let" funktioniert das gleiche wie "Letrec".Aber ändern Sie einfach den Namen in "my-append" und es bricht, weil das Symbol "my-append" im Moment der Auswertung der Lambda-Form noch nicht an irgendetwas gebunden ist (im Gegensatz zu "append", das als eine eingebaute Prozedur definiert wurde)).

Natürlich wird solch eine Form in einer Sprache mit dynamischem Scoping funktionieren, aber das Schema ist lexikalisch (mit Ausnahme von "define" s), und der Grund ist referentielle Transparenz (aber das ist so weit weg, dass ich nur darauf verweisen kann) interessierte Leser zu einem der Lambda Papiere http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AIM-453.pdf).

Quelle

2016-07-13 19:26:00 dercz

Es gibt mehrere Möglichkeiten, dies zu tun. Hier ist ein weiterer:

(define my-reverse 
    (lambda (lst) 
    (define helper 
     (lambda (lst result) 
     (if (null? lst) 
      result 
      (helper (cdr lst) (cons (car lst) result))))) 
    (helper lst '())))

Quelle

2016-07-14 05:41:45

Antwort

Verwandte Themen