Not logged in. · Lost password · Register

Page:  1  2  next 
bRownY
Undefined
Avatar
Member since Nov 2005
601 posts
Subject: Klausur März 2005
Aufgabe 4a)
Schreiben Sie in Scheme eine Funktion insert, die als Parameter ein Symbol symbol,eine flache Liste von Symbolen liste und einen Integer n nimmt. Als Ergebnis soll die Liste zurückgeliefert werden, die entsteht, wenn man das Symbol symbol an der Position n in die Liste liste einfügt                        

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)))
)
"Da geht er hin, einer von Gottes eigenen Prototypen - ein aufgemotzter Mutant, der nie zur Massenproduktion in Betracht gezogen wurde: zu spleenig zum Leben und zu selten zum Sterben."

Hunter S. Thompson
andy
your local λ-dealer
Member since Oct 2005
248 posts
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))))))
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited 5 times, last on 2006-09-15, 18:33 by andy.
bRownY
Undefined
Avatar
Member since Nov 2005
601 posts
ja cool, danke :)

BTW: wieso machst du listanf so kompliziert?

Hab immer bissl Schwächen bei Rekursionen, hab etz auch 10mins gebraucht um deins zu verstehen, aber etz is mir einiges klarer (hoffe ich :)).
"Da geht er hin, einer von Gottes eigenen Prototypen - ein aufgemotzter Mutant, der nie zur Massenproduktion in Betracht gezogen wurde: zu spleenig zum Leben und zu selten zum Sterben."

Hunter S. Thompson
andy
your local λ-dealer
Member since Oct 2005
248 posts
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.
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited 2 times, last on 2006-09-15, 18:39 by andy.
Comrade
THI-Survivor
Avatar
Member since Nov 2005
623 posts
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))))))
"My uzi weighs a ton..."
andy
your local λ-dealer
Member since Oct 2005
248 posts
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)))
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited on 2006-09-15, 18:58 by andy.
Comrade
THI-Survivor
Avatar
Member since Nov 2005
623 posts
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...
"My uzi weighs a ton..."
andy
your local λ-dealer
Member since Oct 2005
248 posts
Quote by Comrade:
die loesung faengt allerdings nicht den Fall ab dass man in n eine ungueltige  Position uebergibt...
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. ^^
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited 5 times, last on 2006-09-15, 19:14 by andy.
Comrade
THI-Survivor
Avatar
Member since Nov 2005
623 posts
Quote by andy:
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.
war auf meine Loesung bezogen...wenn man in n muell uebergibt tuts nicht mehr...


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. ^^
jap,das sollte da nicht hin...
"My uzi weighs a ton..."
andy
your local λ-dealer
Member since Oct 2005
248 posts
Quote by Comrade:
war auf meine Loesung bezogen...wenn man in n muell uebergibt tuts nicht mehr...
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.
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited 2 times, last on 2006-09-15, 19:32 by andy.
Comrade
THI-Survivor
Avatar
Member since Nov 2005
623 posts
z.b. (insert 1 '(1 2 3) 1000)
"My uzi weighs a ton..."
andy
your local λ-dealer
Member since Oct 2005
248 posts
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?
"Destroy your lucrative career as a Java programmer: Learn Haskell!"
This post was edited 2 times, last on 2006-09-15, 19:37 by andy.
Anteru
Mr. Paranoia™
Avatar
Member since Oct 2005
417 posts
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.
Was treibt dich hierher? - Durst und Zufall, zwei zuverlässige Begleiter.
bRownY
Undefined
Avatar
Member since Nov 2005
601 posts
In reply to post #5
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 :) )

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
(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)))
)

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.
(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))
)
"Da geht er hin, einer von Gottes eigenen Prototypen - ein aufgemotzter Mutant, der nie zur Massenproduktion in Betracht gezogen wurde: zu spleenig zum Leben und zu selten zum Sterben."

Hunter S. Thompson
vielleicht
Philipp Caliebe
Member since Oct 2005
259 posts
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...
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Page:  1  2  next 
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen