So mal ein bisschen Denksport :)
Ich bin grad bei der Prüfungsvorbereitung und hab hier ne schicke Aufgabe bei der ich nicht wirklich weiterkomme...
Zu schreiben ist eine Funktion binsuch in Lisp welche eine Liste der Form Baum entgegen nimmt.

Zitat:

Baum-> (a Baum Baum),
Baum-> a

Zitat:

(binsuch ‘(10 (4 1 (6 NIL 7)) (15 NIL (20 16 22)) ) )

Lösung meinerseits hierzu:
Quellcode:(in-package "USER")

(defun binsuch (tree)
    (cond
        ((not(atom (car tree))) NIL) ; Sicherung gegen Falscheingabe
        ((null (car tree)) NIL) ; dito
        ((and
            (cond
                ((null (cadr tree)) T) ; nicht nach links verzweigt
                ((atom (cadr tree)) (< (cadr tree) (car tree))) ; left atomar -> left muss < root sein
                ((binsuch (cadr tree)) (< (car (cadr tree)) (car tree))) ; wenn left ein BSB ist so muss die Wurzel von left < root sein
                (T NIL)
            )
            (cond
                ((null (caddr tree)) T) ; nicht nach rechts verzweigt
                ((atom (caddr tree)) (>= (caddr tree) (car tree))) ; rght atomar -> rght muss >= root sein
                ((binsuch (caddr tree)) (>= (car (caddr tree)) (car tree))) ; wenn rght ein BSB ist so muss die Wurzel von rght >= root sein
                (T NIL)
            )
         ) T)
        (T NIL) ; sonst kein binärer Suchbaum
    )
) genutzter Interpreter: GNU CLISP 2.43
Meistert den Test auch passabel.

Problematisch ist allerdings, dass ich nur mit der unmittelbaren Wurzel vergleiche. Dadurch könnte man zB den Baum
‘(10 (4 1 (6 NIL 7)) (15 8 (20 16 22)) )
eingeben und würde wahr geliefert bekommen, was ja totaler Käse ist, weil die 8 ja kleiner 10 ist und damit nix im rechten Teilbaum verloren hat.
Mir fällt allerdings kein Weg ein wie ich einen Wert mit sämtlichen übergeordneten Wurzeln vergleichen kann (und das auch noch "verzweigungsrichtig"). Jemand ne Idee?

2.
Ich hatte vorher ne Lösung geschrieben in der ich per
Quellcode:(setq root (car tree) left (cadr tree) rght (caddr tree)) Variablen belegt hatte um nicht so nen Code zu produzieren wie er es jetzt ja doch ist.
Problem war, das die Variablen anscheinend global definiert wurden und damit, da sie am Anfang der Funktion festgelegt wurden, bei der Rückkehr aus der Rekursion den zuletzt zugewiesenen Wert beibehalten haben. Gibts irgendeine Möglichkeit Variablen nur im Scope einer Funktion zu definieren (ich kann mir kaum vorstellen dass es das nicht gibt)?

The C language combines all the power of assembly language with all the ease-of-use of assembly language.
"humorig is n blödwort :>" by -CarniGGeLjumpR-

das nennt sich dynamic scope und war (laut meiner compilerbau-professorin) ein sprachbug in lisp, der zum feature erklärt wurde ;)
es gibt wohl lisp-implementierungen, die "lexical scope" haben - was wohl das selbe ist wie static scope (was man aus richtige programmiersprachen kennt). kA, wie deine das handled und wie man ggf forcieren kann, aber so hast du zumindest nen ansatzpunkt ;)

caedes

Deutschland rückt nach Einschätzung der Sicherheitsbehörden im Superwahljahr verstärkt ins Visier von Terroristen.

Quellcode:(setq bar 23)

(defun foo ()
  (declare (special bar))
  bar)

(foo)
; 23

(let ((bar 42))
  (declare (special bar))
  (foo))
; 42

\o tanz den naziprau! o/

And more than ever, I hope to never fall,
Where enough is not the same it was before

Danke euch beiden, besonders dir don. let war genau wonach ich gesucht habe. Finde doch sehr eigenartig, dass unser Prof da nix zu gesagt hat. Wobei 3 Vorlesungen auch bisschen mager sind... Hab auch mal bezüglich des declare special nachgekuckt, hab noch nicht so ganz verstanden was es genau macht. Mal sehn ob ich noch die Zeit finde mich da noch etwas tiefer einzuarbeiten, weil für die Prüfung selbst wirds nicht viel bringen (da die wahrscheinlich den Schwerpunkt auf Prolog legen wird, statt auf Lisp) und es stehen ja auch noch einige andere an, die ordentlich bestanden werden wollen ;)

Zum ersten Problem hat sich auch ne "Lösung" gefunden. Ziemlich straightforward... Der linke und rechte Teilbaum wird auf eine Ebene runtergebrochen (im Sinne von einer Listenebene) und dann wird geschaut ob alle Elemente in der entstandenen Liste kleiner bzw größer/gleich dem aktuellen Wurzelknoten sind. Damit wird quasi schon vor der Rekursion eine Gültigkeit des Baumes forciert.

Hier noch das Listing, falls mal ne arme Seele ein ähnliches/gleiches Prob hat:
Quellcode:(in-package "USER")

; alle kleiner als
(defun alllt (a x)
    (cond
        ((null a) T)
        ((atom a) (< a x))
        (T (and (< (car a) x) (alllt (cdr a) x) ) )
    )
)

; alle groesser/gleich
(defun allge (a x)
    (cond
        ((null a) T)
        ((atom a) (>= a x))
        (T (and (>= (car a) x) (allge (cdr a) x) ) )
    )
)

; Flat-wrapper
(defun Flatten (x) (Flat x NIL))

; breche Liste a auf eine Ebene herunter und haenge b an
(defun Flat (a b)
    (cond
        ((Null a) b)
        ((Atom a) (Cons a b))
        (T (Flat (Car a) (Flat (Cdr a) b)))
    )
)

; pruefe binaeren Suchbaum
(defun binsuch (tree)
    (let ((root (car tree)) (left (cadr tree)) (rght (caddr tree)))
        (and
            (alllt (Flatten left) root) ; links muss alles kleiner sein
            (allge (Flatten rght) root) ; rechts muss alles groesser/gleich sein
            (cond
                ((not(atom root)) NIL) ; Sicherung gegen Falscheingabe
                ((null root) NIL) ; dito
                ((and
                    (cond
                        ((null left) T) ; nicht nach links verzweigt
                        ((atom left) (< left root)) ; left atomar -> left muss < root sein
                        ((binsuch left) (< (car left) root)) ; wenn left ein BSB ist so muss die Wurzel von left < root sein
                        (T NIL)
                    )
                    (cond
                        ((null rght) T) ; nicht nach rechts verzweigt
                        ((atom rght) (>= rght root)) ; rght atomar -> rght muss >= root sein
                        ((binsuch rght) (>= (car rght) root)) ; wenn rght ein BSB ist so muss die Wurzel von rght >= root sein
                        (T NIL)
                    )
                ) T)
                (T NIL) ; sonst kein binaerer Suchbaum
            )
        )
    )
)


The C language combines all the power of assembly language with all the ease-of-use of assembly language.
"humorig is n blödwort :>" by -CarniGGeLjumpR-

irgendwie bin ich doch froh, dass ich haskell machen durfte statt lisp (und prolog) -_-

caedes

Deutschland rückt nach Einschätzung der Sicherheitsbehörden im Superwahljahr verstärkt ins Visier von Terroristen.

Aber Prolog ist doch wat feines ^^

The C language combines all the power of assembly language with all the ease-of-use of assembly language.
"humorig is n blödwort :>" by -CarniGGeLjumpR-