listen mit cons

MisaghZ
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 133
Registriert: 11. Okt 2007 15:50

listen mit cons

Beitrag von MisaghZ »

Hallo,
ich versuche nun seit einiger Zeit die mirror-aufgabe von der Übung1 zu lösen.
ich wollte das ganze so lösen, dass eine liste bilde mit
cons(hd(liste), mirror(tl(liste)), hd(liste))
wohingegen mirror dann wieder rekursiv das selbe macht mit dem tail der liste

allerdings erwartet cons immer 2 parameter
ist es nicht möglich, etwas wie "list" in scheme zu verwenden, wo es eine beliebige anzahl an parametern geben kann?



ich habe später auch versucht das ganze so zu lösen, indem ich schrieb:
cons(hd(liste), cons(mirror(tl(liste)), hd(liste)))

allerdings tritt hier das problem auf, dass mirror(tl(liste)) überprüft ob:
"liste empty ist"
dies ist nur notwendig um im ersten schritt zu überprüfen, ob der input nicht die leere liste ist.

allerdings könnte, verifuns meinung diese abfrage auch in einem der rekursiven aufrufe wahr werden.
somit entstünde dann eine liste mit:
cons(hd(liste), cons(empty, hd(liste)))
was natürlich nicht gewollt ist.
desshalb sagt mir dass cons nur parameter vom typ @I haben möchte


wie kann ich dieses Problem lösen?

dschneid
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: listen mit cons

Beitrag von dschneid »

Gibt es cons überhaupt im Zusammenhang mit Listen? Ich habe das beim schnellen Überfliegen der Folien nur für S-Expressions gefunden. Soweit ich weiß, arbeitet man bei Listen doch mit :: (was aber genau das selbe ist wie cons in Scheme, nur in anderer Syntax).

Benutzeravatar
cofi
Mausschubser
Mausschubser
Beiträge: 86
Registriert: 22. Sep 2009 12:07

Re: listen mit cons

Beitrag von cofi »

Dein Scheme Ansatz mit `list` passt nicht, da wuerdest du die Listen nur verschachteln - auch moeglich, du musst nur eine Funktion zum flatten danach loslassen, die will aber auch erstmal geschrieben werden ;)

Dein `cons`-Code stimmt - neben dschneids Einwand - auch nicht, da cons als 2. Parameter eine Liste will, nicht als 1.

Du suchst eine Funktion, die Listen appended - siehe 1.2a.

Nathan Wasser
Kernelcompilierer
Kernelcompilierer
Beiträge: 430
Registriert: 16. Okt 2009 09:48

Re: listen mit cons

Beitrag von Nathan Wasser »

Ich bin mir nicht ganz sicher was Sie genau mit "cons" meinen. Wenn damit der Listenkonstruktor :: gemeint ist, dann:

:: ist eine infix Funktion vom Typ \(@A \times list[@A] \rightarrow list[@A]\). Dies bedeutet, dass das linke Argument von einem beliebigen Typ ist, das rechte Argument eine Liste mit Elementen dieses Typs ist, und das Ergebnis wiederum eine Liste mit Elementen dieses Typs ist. Die Selektoren \(hd\) und \(tl\) geben jeweils den Kopf und Rumpf einer Liste zurück: \(hd(x :: k) = x\), \(tl(x :: k) = k\). Somit hat \(hd\) den Typ \(list[@A] \rightarrow @A\) und \(tl\) den Typ \(list[@A] \rightarrow list[@A]\). Die Prozedur \(mirror\) muss wie angegeben den Typ \(list[@A] \rightarrow list[@A]\) haben. Der Term \(cons(hd(liste), cons(mirror(tl(liste)), hd(liste)))\), also \(hd(liste) :: mirror(tl(liste)) :: hd(liste)\) ist also nicht Typkorrekt. Insbesondere ist \(mirror(tl(liste)) :: hd(liste)\) nicht Typkorrekt.

Wenn Sie wollen, können Sie gerne die Prozedur probeweise in Scheme implementieren. Da Scheme auch Listen von Elementen verschiedenen Typs erlaubt, gibt es dort keinen Typfehler. Die Prozedur wird aber vermutlich nicht das berechnen, was Sie wollen. Insbesondere berechnen \((list\ (car\ liste)\ (mirror\ (cdr\ liste))\ (car\ liste))\) und \((cons\ (car\ liste)\ (cons\ (mirror\ (cdr\ liste))\ (car\ liste)))\) sogar unterschiedliche Werte. (Die auch beide unterschiedlich zur gewünschten gespiegelten Liste sind.)

In \(\mathcal{L}\) sind übrigens keine Prozeduren mit variabler Anzahl an Argumenten möglich. Somit kann es keinen \(list\) Operator wie in Scheme geben.

Antworten

Zurück zu „Archiv“