Fachrat Informatik - Forum

Quoted

Original von motja
weißt jemand, wie die Listen in Scheme definiert sind?

klick <-- In Kapitel 2 findest du alles, was du brauchst - zumindest die Definition von Listen

Also, sooo eindeutig geht das aus Kapitel 2 nicht hervor, da steht nur dass dir cons-Prozedur mit nil enden muß um eine Liste zu sein.

Was ist aber, wenn es vorher eine Abzweigung gab?

z.B. (cons (cons 1 2) (cons 3 nil))

Ist das dann auch eine Liste oder eher ein Baum?
Der Zweig (cons 1 2) hört ja nicht mit nil auf, ist also per Definition KEINE Liste.

PS: Hilfreich war für mich auch die Seite
Scheme

(cons 1 2) ist keine Liste, richtig.
Spätestens wenn im dritten Semester verkettete Listen an die Reihe kommen, wird diese Aufgabe zum Kinderspiel. Ok, aber das kommt nächstes Jahr
Stell dir eine Liste mit n Elementen als n Kästchen vor. Jedes Kästchen hat zwei Felder, ein Datenfeld und ein Zeigerfeld. Der Zeiger zeigt auf das nächste Kästchen, oder ist null (nil) wenn kein weiteres Kästchen folgt.
Will man 1 2 nun in eine Liste packen, sieht das also so aus:

1_-> 2_\ wobei -> jetzt der Zeiger auf das nächste Elemtn sein soll und \ der Nullzeiger.

(cons 1 2) ist demnach keine Liste, weil im zweiten Feld des "Kästchens" kein weiterer Zeiger auf das nächste Kästchen steht, sondern weitere Daten.

Wenn man sich (cons (cons 1 2) (cons 3 nil)) anschaut, dann musst du dir überlegen, wann bei einem cons als zweites Element ein neues cons steht, damit also quasi ein neuer Zeiger auf ein nächstes Kästchen -> dann ist dieser Teil eine Liste (und dass musst du natürlich für alle Teilstrukturen testen ).

Die Erklärung mit den Zeigern mag vielleicht nicht 100%ig korrekt sein, da mir die interne Struktur von Scheme leider nicht so geläufig ist, wie ich es mir wünschen würde, aber ich hoffe, zum Verständnis hat es etwas beigetragen (:

Für den Notfall benutze (list? (cons ... ) ) um erstmal grob abschätzen zu können was eine Liste ist und was nicht, die Erklärungsfindung ist dann vielleicht einfacher.

Allerdings muss auch ich sagen, dass es sehr unlogisch ist, mit dem eingeführten Kästchen Schema von cons auf Liste zu kommen. Und sofern nicht in der Vorlesung gesagt worden wäre( Grund die Zeigerarithmetik ist ganz anders und ähnelt eher einem Array ), das Scheme versucht eine Liste aus cons Ausdrücken zu bauen, sofern dies möglich ist, heisst man "terminiert" es logisch mit NULL am Ende, wofür es dann wohl 2 Varianten gibt, wäre es nach wie vor uneinsichtig.

Quoted

Original von Philipp
( Grund die Zeigerarithmetik ist ganz anders und ähnelt eher einem Array )

Die Zeigerarithmetik ähnelt eher einem Array?
Meiner Erfahrung nach, stellt sich das eher so da:
Array: Reserviert x stellen im Speicherbereich der Länge n, und wenn auf Element 7 zugegriffen werden soll, dann gehe nach Anfang + 7 * n.
Nix Zeiger.
(Verkettet) Liste: Eine Liste besteht aus Elementen, welche aus einem Datenfeld und einem Zeigerfeld bestehen. Es gibt einen ausgezeichnetes Feld der Liste, den sogenannten Kopf. Der Verweist auf ein weiteres Element der Liste, dieses auf ein neues usw. bis zum letzten Element, dass einen Zeiger ins Nirvana hat.

So würde ich das ganze mal ganz grob umschreiben, korrigiert mich, wo ich falsch liege.

Quoted

Und sofern nicht in der Vorlesung gesagt worden wäre, das Scheme versucht eine Liste aus cons Ausdrücken zu bauen, sofern dies möglich ist, heisst man "terminiert" es logisch mit NULL am Ende, wofür es dann wohl 2 Varianten gibt, wäre es nach wie vor uneinsichtig.

Kannst du diesen Satz ggf. mal entschachteln, ich steig nämlich nicht durch (Also das mit den zwei Varianten und dem uneinsichtig)

@Markus

Wenn man Mehrdimensionale Arrays nimmt, dann ähnelt das schon von dem Kästchenschema sehr cons ( Primitives Mehrdimensionales Array ). Ein Array ist übrigens auch ein Zeiger. Und zwar enthält enthält es die Adresse des ersten Segments. Über die Arithmetik greift man dann auf die nächsten Segmente zu ausgehend von der Adresse des ersten Zeigers. Eine Liste ist nur eine sinnvollere Variante wenn man oft reallociert, weil sich die Listen durch den ganzen HEAP ziehen kann, während man bei Arrays immer einen gesamten Block ( Alter Block + neues Segment ) reallocieren muss.
Ansonsten gibt es da keinen Unterschied. Ein Array kann genauso einen ganzen Datenblock beherbergen z.B. von struct{}; .
Ist aber auch egal und gehört hier wohl gar nicht rein.

Von Scheme wird sowohl (cons 1 (cons 1 '() ) ) als auch (cons (cons 1 1 ) '() ) als Liste durch list? erkannt, wenn gleich zweites Output nicht nach Liste aussieht.

Philipp, Liste ungleich Heap, Liste ungleich Array!
Liste und Array sind total unterschiedliche Datenstrukturen, bei einer Liste sind die Daten absolut und nicht über Adressarithmetik referenziert. Daher die Zeiger. Beim Array gibt eine Referenz auf den Anfang, von mir aus noch aufs Ende und das war's.
Ich empfehle zum Verständnis von Listen zum Beispiel wiki. Und für Scheme das hier.
Und natürlich die Vorlesung zu Datenstrukturen und Algorithmen.

Und wenn du das mit den Listen drauf hast, wirst du auch verstehen, warum (cons (cons 1 1 ) '() ) eine Liste ist, und (cons 1 1 ) nicht

Quoted

Original von Markus
(und dass musst du natürlich für alle Teilstrukturen testen ).

(:

Markus,
soweit alles klar, nur Dein eingeklammerter Satz verwirrt mich noch etwas.
Was meinst Du mit "Teilstruktur"?

Im Wiki steht:
"Außerdem ist ein Paar, dessen cdr eine Liste ist eine Liste"

Das heisst für mich, ich muss nur die cdr's betrachten. Ob sich vom car eine neue Liste oder irgendwas "abspaltet" ist egal.

Also ist mein beispiel von oben (cons (cons 1 2) (cons 3 '())) demnach auch eine Liste.

#t oder #f?

Quoted

Original von Kandidat
Also ist mein beispiel von oben (cons (cons 1 2) (cons 3 '())) demnach auch eine Liste.

#t oder #f?

#f
Markus meint mit Teilstruktur sicherlich alle Listen innerhalb einer anderen Liste. Du musst also rekursiv alle Listen prüfen, bis keine Liste mehr in einer anderen enthalten ist.
Zu deinem Beispiel: Weil die "Unterliste" (Teilstruktur) (cons 1 2) selbst keine Liste ist, ist die Gesamtliste auch keine Liste.

Quoted

Original von migu
Weil die "Unterliste" (Teilstruktur) (cons 1 2) selbst keine Liste ist, ist die Gesamtliste auch keine Liste.

Ja, so dachte ich nach Markus posting auch.

Aber nach der Wiki-Definition IST es eine Liste.

Und wenn ich mein Beispiel mit list? überprüfe bekomme ich ein #t

Quoted

Original von Kandidat
Aber nach der Wiki-Definition IST es eine Liste.

Und wenn ich mein Beispiel mit list? überprüfe bekomme ich ein #t

Ja, das ist in der Tat merkwürdig.
Nach Möglichkeit sollte man sich an die Definition aus der Vorlesung halten. Vor allem natürlich, wenn das in der Aufgabenstellung so gefordert wird.

Wichtig ist nur die äußere Struktur. Was an den einzelnen Listenprositionen für Objekte hängen ist irrelevant.

Quoted

Original von Kandidat
Markus,
soweit alles klar, nur Dein eingeklammerter Satz verwirrt mich noch etwas.
Was meinst Du mit "Teilstruktur"?

Im Wiki steht:
"Außerdem ist ein Paar, dessen cdr eine Liste ist eine Liste"

[...]

Also ist mein beispiel von oben (cons (cons 1 2) (cons 3 '())) demnach auch eine Liste.

#t oder #f?

Hi, das mit den Teilstrukturen war schelcht ausgedrückt von mir, sorry.
Ich meinte das so: Wenn der Kopf eine Liste ist, also ein Paar aus "Daten und Zeiger" (auch wenn das jetzt so nicht korrekt sein mag für Scheme, s.o.) und das ganze eine Liste sein soll, dann muss das nächste Element (und die folgenden) auch so aufgebaut sein. Das meinte ich mit Teilsturktur, das war schlecht formuliert. Wesentlich besser ist die Formulierung von wiki, also "Außerdem ist ein Paar, dessen cdr eine Liste ist eine Liste".

In deinem Beispiel hast du ein Paar (das erste cons) das im cdr-Feld auf ein weiteres Paar verweist, und im car Feld ist ebenfalls ein cons-Paar. Was im car-Feld steht, kannst du als "irgendwelche" Daten ansehen. Diese Daten können natürlich wieder eine Liste sein, müssen aber nicht

Ich hoffe, dass ist jetzt klarer? (:

Eine Scheme-Liste hat folgende Eigenschaften:
1. Sie ist leer ()
oder
2. Sie enthält einen oder mehrere Elemente, wobei diese Elemente nur durch Leerzeichen voneinander getrennt sind, also nicht durch Punkte, Kommata, etc.

Ich erinnere mich daran, dass ich die Frage, ob z.B.
(cons (cons 1 2) (cons 3 (cons 4 (cons (cons 5 6) (cons 7 (cons (cons 8 9) ’()))))))

eine Liste ist oder nicht immer dadurch gelöst habe, indem ich mir die Endform davon in der Ausgabe angesehen habe.

so soll eine Liste in der Ausgabe aussehen:
(1 2 3 (5 4 6) 3 2)
oder so:
(1 2 3 4 5 6 7 8 )
oder so:
()
aber niemals so:
(1 . 2 3 4 5)
oder
(1 2 3 4 . 5)
ich hoffe, es ist klar, was ich sagen wollte - Scheme ist für mich schon länger her und ich habe auch kein drScheme mehr auf meinem PC.

Kann mir jemand mal eben sagen wie ich einer Liste immer
ein bestimmtes Element anhängen kann?

da wird dir wohl append weiterhelfen.. einfach zwei listen als argumente angeben und schon hast du deine zusammengefügte liste.
Wenn du nur ein Element und nicht ne ganze Liste hinzufügen willst einfach (list element) und das dann als an die Funktion.

Append steht auch unten drauf, also darf man das ruhig benutzen.

also muss ich, sofern ich nur eine liste und ein einzelnes element habe trotzdem sowas wie
append (list 1 2 3 4) (list 5) machen richtig?

Also irgendwie geht das so nicht so richtig, ich bekomme dann eine liste die wie folgt aussieht: (x x x x . x) und dann weigert der sich beim 2 ten mal ein element dran zu hängen...

Quoted

Original von Kojack
also muss ich, sofern ich nur eine liste und ein einzelnes element habe trotzdem sowas wie
append (list 1 2 3 4) (list 5) machen richtig?

Richtig.
Das Problem ist, dass Scheme nur einfach verkettete Listen kennt. D.h. es ist nur möglich direkt auf das erste element der Liste zuzugreifen und ein element vor die Liste zu hängen, will man an das letzte Element muss man sich bis zum ende hangeln und das anhängen ist auch nicht so trivial.

einfach:
(cons 1 (list 2 3 4 5))

kompliziert:
(append (list 1 2 3 4) (list 5))

Ja aber man kann doch mit append zwei listen zusammenfügen oder nicht, wenn also zwei listen bekannt sind, kann man sie doch auch an einander hängen...
Mein Problem ist, dass ich eine fehlermeldung bekomme wenn ich das so mache wie du:
(append (list 1 2 3 4) (list 5))

kann man anstatt der zahl "5" nun auch z.b. "car x" als element der liste eingeben? dabei sagt er mir das geht nicht.