Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Klausur März 2005
Hab das mal versucht zu bauen, war mein erstes scheme programm :red: … kann mal jemand schauen ob des irgendwie schneller ginge, aber so vom ansatz her passt das doch, oder? funktionieren tuts ( abgesehen davon dass er nicht schaut ob die liste ueberhaupt ueber n stellen verfuegt )
(define (insert symbol liste n)
(define (listend ende cnt)
(if (= cnt n) ende
(listend (cdr ende) (+ cnt 1))))
(define (listanf anf ende cnt)
(if (= cnt n) anf
(listanf (append anf (list (car ende))) (cdr ende) (+ cnt 1))))
(append (listanf '() liste 1) (cons symbol (listend liste 1)))
)Garnicht schlecht, du könntest aus Gründen der Wiederverwendbarkeit
(define (drop n l)
(cond ((zero? n) l)
(else (drop (- n 1) (cdr l)))))
(define (take n l)
(cond ((zero? n) '()
(else (cons (car l) (take (- n 1) (cdr l))))))verwenden, dann wäre
(define (insert sym l n)
(append (take n l) (list sym) (drop n l)))BTW: wieso machst du listanf so kompliziert? im rekursiven Fall einfach vorne dran-consen, dann brauchste auch das 1. Argument (anf) nicht mehr:
(cons (car ende) (listanf (cdr ende) (+ cnt 1))))Ach ich weiß: du dachtest tail-recursive reisst dir hier was? Das machste dir mit dem append auf anf leider sowieso mehrfach zunichte, aber wenn du das neue anf durch vorne dranconsen bildest, hättest du ein bisschen was gewonnen. Jetzt musst du halt mit reverse drauf um wieder die Reihenfolge zu kriegen die du in insert brauchst.
Hier in dem Beispiel lohnt tail-rec aber wirklich nicht weil du den gewonnen stack-space sowieso wieder mit dem anf-Argument verbrauchst, dazu kommt noch das Stack-Allocations in funktionalen Sprachen teilweise hammer optimiert werden (geht häufig auch nichtmehr über den eigentlichen Stack).
Ausserdem würde das danach notwendige reverse ungefähr nochmal genauso viel fressen…
So ne Taktik würde sich allerdings lohnen wenn du die meiste Zeit auf solchen snoc-Listen (also halt eigentlich verkehrt geordeneten) arbeitest und dann fürs Endresultat ein reverse machst. Mit den snoc-Listen haste ja O(1) Zugriff aufs letzte Element und kannst dementsprechend ein effizientes (O(n) mit n=Laenge der drangehängten, nicht der vorherigen! Liste, also meistens sogar O(1) in Bezug auf die Eingabegrössen des Problems) reverse-append draufmachen.
Schneller gehts natürlich ohne append:
(define (insert sym l n)
(cond ((null? l) (list sym)) ; deckt hiermit auch den fall (length l)<n ab
((zero? n) (cons sym l))
(else (cons (car l) (insert sym (cdr l) (- n 1))))))ja cool, danke 
Hab immer bissl Schwächen bei Rekursionen, hab etz auch 10mins gebraucht um deins zu verstehen, aber etz is mir einiges klarer (hoffe ich :)).
Dann war ne Optimierung durch Tail-Rekursion garnicht deine Absicht? Hmm, dann kannste den Abschnitt meines Posts wohl ignorieren. ^^
BTW, für die Leute die schon mit lazy-Evaluation zu tun hatten: hier ist tatsächlich amortisiertes O(1) für append möglich und sogar gängige Praxis. Insofern bin ich geneigt zu sagen das die erste Lösung mit take/drop hier sogar die beste wäre.
Habs so…
(define (insert symbol liste n)
(cond ((null? list) (list symbol))
((= n 1) (cons symbol liste))
(else (cons (car liste) (insert symbol (cdr liste) (- n 1))))))
Hmm, wir habens wohl unterschiedlich aufgefasst. Ich füge an nullbasierter “Position” n (also quasi Index), du an einsbasierter “Position” n ein. Was sagt denn die Musterlösung?
Ach sehe grad bRownY hats auch so interpretiert. Die andere Variante wäre dann mit einsbasierter “Position” n:
(define (insert sym l n)
(append (take (- n 1) l) (list sym) (drop (- n 1) l)))die loesung faengt allerdings nicht den Fall ab dass man in n eine ungueltige
Position uebergibt…
In der Musterloesung tun sie das allerdings auch nicht…sagen aber dass bei ner Leeren liste auch ne leere zurueck gegeben wird…
Welche Loesung meinst du? Meine fängt halt keine negativen n ab.
Take und drop könnte man noch um nen null? Fall erweitern, so das die andere Variante auch n>(length l) verkraften würde.
Deine verhält sich doch fast genauso wenn ich das richtig sehe. Halt bis auf den n=0 Fall, aber der ist bei einsbasierten Positionen ja wie negative bei nullbasierten.
BTW: den Schreibfehler „list“ stattt „liste“ im ersten Fall haste hoffentlich bemerkt, oder? „list“ ist ne Funktion, deswegen gäbe das nichtmal nen Fehler und (null? list) ist immer #f. ^^
war auf meine Loesung bezogen…wenn man in n muell uebergibt tuts nicht mehr…
jap,das sollte da nicht hin…
Was für „Muell“ meinst du? Hört sich jetzt nicht nach negativen Zahlen an. :>
Wenn du Objekte eines anderen Typs meinst, kannste das als Typfehler werten und erstmal ignorieren (Fehler auf dem Niveau könnte man relativ leicht mit entsprechenden Tools aufspüren).
Ach hab grade noch gemerkt das unsere beiden Lösungen sogar nicht-positive Zahlen verkraftet. Gehen dann halt einfach solange durch bis nil kommt und wird hinten angefügt. Wobei man das eigentlich schon als Fehler werten könnte.
z.b. (insert 1 '(1 2 3) 1000)
Ach du meinst du kriegst die “freigelassenen” Elemente nicht? Hab die Spezifikation ehrlich gesagt nicht so verstanden das das verlangt ist. Also wenn du ein Element an ne Position einer Liste einfügst die grösser als die Länge der Liste ist, ist das entweder ein Fehler oder ist für mich das Verhalten unserer Funktionen.
Konkret:
Was soll denn sein wenn du an Position 2 der leeren Liste was anfügst? ('() 2) oder (2) oder Fehler?
Ich tät mir jetzt auch nicht den Kopf drüber zerbrechen. Das Fach heisst Algorithmik - wir schreiben hier kein Betriebssystem sondern sollen Algorithmen verstehen. Fehlerabfragen zählen da wohl kaum dazu und ich bezweifle auch dass dir da irgendwer dann eins auf den Deckel gibts wenn du nicht jede einzelne Benutzereingabe überprüfst (never trust user input!) 
Denke mal wenn die Fehlerbehandlung wollen dann werden die es auch explizit dazuschreiben.
So hab etz auch noch die b) und c) gemacht ( aber wieder in meiner umständlichen form, aber wenn ichs anders probier dauerts ewig, da schreib ich in der klausur lieber ein bisschen mehr 
)
[quote]
Schreiben Sie mit Hilfe der Funktion insert aus Teilaufgabe a) eine Funktion insert-all, die als Parameter ein Symbol symbol und eine flache Liste von Symbolen liste nimmt. Als Ergebnis soll eine Liste mit allen Listen zurückgeliefert werden, die entstehen, wenn man das Symbol symbol an jeder beliebigen Position in die Liste liste einfügt[/quote]
(define (insert-all symbol liste)
(define (build list n)
(cond ((zero? n) list)
(else (build (cons (insert symbol liste n) list) (- n 1))))
)
(build '() (+ 1 (length liste)))
)[quote]
Schreiben Sie mit Hilfe der Funktion insert-all aus Teilaufgabe b) eine Funktion insert-all-lists, die als Parameter ein Symbol und eine Liste von flachen SymbolListen listen nimmt. Als Ergebnis soll eine Liste mit allen Listen zurückgeliefert werden, die entstehen, wenn man das Symbol symbol an jeder beliebigen Position aller in der Liste liste enthaltenen Listen einfügt. Der Einfachheit halber sollen in der Ergebnisliste auch Wiederholungen möglich sein.[/quote]
(define (insert-all-lists symbol listen)
(define (build list lists n)
(cond ((zero? n) list)
(else (build (append list (insert-all symbol (car lists)))
(cdr lists) (- n 1))))
)
(build '() listen (length listen))
)
Jetzt will ich aber meins auch mal bewertet haben g
(define (insert symbol liste n)
(cond ((null? liste) (list symbol))
((= n 1) (cons symbol liste))
(else (cons (car liste) (insert symbol (cdr liste) (- n 1))))))
(define (insert-all symbol liste)
(define (fn pos)
(cond ((> pos (+ (length liste) 1)) '())
(else (cons (insert symbol liste pos) (fn (+ pos 1))))))
(fn 1))
(define (insert-all-lists symbol listen)
(define (fn liste)
(cond ((null? liste) '())
(else (cons (insert-all symbol (car liste)) (fn (cdr liste))))))
(fn listen))Was mich eigentlich daran noch stört sind die defines… Wie macht man das ohne, weil ich finde sieht net schick aus…
Baust dir deine map-Struktur unnötigerweise selber, aber wenigstens nicht sonderlich ineffizient. Übrigens gilt hier das gleiche wie oben: du musst nicht immer nen Akkumulationsargument mitschleppen das du tailrec kriegst, das ist so auf bestimmten Implementierungen sogar langsamer als die normale Variante. :>
Hier mal für nullbasiertes insert:
(define (enumFromTo a b)
(cond ((> a b) '())
(else (cons a (enumFromTo (+ a 1) b)))))
(define (insert-all sym l)
(map (lambda (n) (insert sym n l)) (enumFromTo 0 (length l))))Hier wärs besonders leicht mit map:
(define (insert-all-lists sym lists)
(apply append (map (lambda (l) (insert-all sym l)) lists)))Hatte ich auch so in etwa (weiß jetzt nimmer wie ichs genau hatte), nur irgendwie sah dann die Liste, die am Ende raus kam net so aus, wie sie aussehen sollte! Aber vielleicht hatte ich auch nen Denkfehler drin. Zumindest hatte ich den Gedanken mit dem map g
ich finde die defines im define etz au ned grad so toll, aber ich machs lieber so auch in der klausur ^^ weil dann muss ich ned vorher um 10 ecken denken, un mach hoffentlich so au weniger fehler … will ja hier etz erst mal kein scheme opt-code coder werden 
sorry jungs, aber den map befehl hat ich noch nicht angeschaut :red: ^^ wird scho bissl knapp das alles bis montag aber vll reichts ja fuer 50%, und wenn nicht, gibt ja noch nen versuch :*)
[edit: ] und sorry fuer doppelpost