Lisp - binary search tree

[DocEW]

Hi,

ich schlage mich gerade mit LISP rum und mag es nicht. ;)
Folgendes einfaches Problem: Einfügen in einen binären Suchbaum. Hier erstmal mein Ansatz:(defun insertBST(element bst)
( setf (first (rest (first bst))) (+ 1 (first (rest (first bst))))) ; increase_element_count();

(let (( current (first(first bst)))
( left (first(rest bst)))
( right (rest (rest bst))) )

( cond ( (<= element current) ; if ( element <= current )
( write-string "inserting LEFT..." )
( cond ( (eq (first (rest bst)) nil ) ; if ( current->leftSubtree == null )
(write-string "leer ") ;
(setf (first (rest bst)) ( cons (cons element '(1)) '(NIL NIL)) ) ; insert_here_as_left_subtree();
)
( t ; else
(write-string "nichtleer ") ;
(insertBST element (first (rest bst))) ; insertBST(element leftSubtree)
)
)
)
( t
( write-string "inserting RIGHT..." )
; ...
)
)
)
)

gestestet habe ich es folgendermaßen:[1]> (load 'test.cl)
;; Loading file test.cl ...
;; Loaded file test.cl
T
[2]> (setf tree '( (5 1) NIL NIL ))
((5 1) NIL NIL)
[3]> (insertBST 3 tree)
inserting LEFT...leer
((3 1) NIL NIL)
[4]> tree
((5 2) ((3 1) NIL NIL) NIL)
[5]> (insertBST 1 tree)
inserting LEFT...nichtleer inserting LEFT...leer

*** - Lisp stack overflow. RESET
[6]>
Also beim ersten Mal klappt es und dann irgendwie nicht mehr?! Keine Ahnung... ich raff's einfach nicht, sitzt da schon 3 Stunden dran! :( Wäre cool wenn jemand helfen könnte.
Achso, noch zum Format vom Baum:((Element AnzahlElementeInDiesemUnterbaum) linkerUnterbaum rechterUnterbaum)

[HellHorse]

Muss ehrlich gestehen ich seh nicht zu 100% durch und kenne nur Scheme und nicht Common Lisp.

Kann es sein, dass du das cond falsch hingekriegt hast? Ich weiss nicht wie es in Common Lisp aussieht, aber in Scheme würde das so nicht hinhauen. Bist du sicher, dass du mit setf auch pairs/Listen modifizieren kannst?

Wenn du schon:

( left (first(rest bst)))

dann brauche es auch und mach nicht

(eq (first (rest bst)) nil )

sondern

(eq left nil )

Ich kenn mich mit CommonLisp nicht genau aus und weiss nicht ob es einen Test auf nil gibt und ob er case sensitiv ist *hint*, aber in Scheme kannst du mit null? prüfen ob eine Liste leer ist.

Ich habe mal kurz etwas in Scheme gemacht, und es scheint zulaufen. Habe zwei Versionen von insert anzubieten. Eine einfache ohne Nebeneffekte und eine komplizierte mit Nebeneffekten.

(define (BST-search node value)
(if (null? node)
#f
(let (
(current (node-value node)))
(cond
((< value current) (BST-search (left-tree node) value))
((> value current) (BST-search (right-tree node) value))
(else #t))
)))

(define (BST-insert node value)
(if (null? node)
(create-empty-node value)
(let (
(current (node-value node))
(left (left-tree node))
(right (right-tree node)))
(if (< current value)
(create-node left current (BST-insert right value))
(create-node (BST-insert left value) current right))
)))

(define (BST-insert! node value)
(let (
(current (node-value node))
(left (left-tree node))
(right (right-tree node)))
(cond
((> current value)
(if (null? left)
(set-left-tree! node (create-empty-node value))

(BST-insert! left value)))
((< current value)
(if (null? right)
(set-right-tree! node (create-empty-node value))
(BST-insert! right value)))
)))

(define (node-value node)
(cadr node))

(define (left-tree node)
(car node))

(define (right-tree node)
(caddr node))

(define (set-right-tree! node newnode)
(set-car! (cddr node) newnode))

(define (set-left-tree! node newnode)
(set-car! node newnode))

(define (create-node left value right)
(list left value right))

(define (create-empty-node value)
(list '() value '()))

;; (define tree (create-empty-node 5))
;; (set! tree (BST-insert tree 7))
;; (set! tree (BST-insert tree 6))
;; (BST-insert! tree 7)

Ist alles bloss minimal getested.

Baumformat:

linkerUnterbaum element rechterUnterbaum

[DocEW]

Hi Hellhorse,

danke für deine Tips. Der nil-Test war es nicht. Die ganzen "let"s habe ich rausgeschmissen, hat aber auch nix gebracht. Keine Ahnung was das Problem ist. Ich raff's nicht. Es muß irgendein Seiteneffekt sein: Ich habe mal den Baum, den das Programm nach einmaligem Einfügen als Ergebnis rausspuckt ((5 2) ((3 1) NIL NIL) NIL)mit copy & paste kopiert und dann Lisp neugestartet und etwas in diesen Baum eingefügt und es geht. Wenn ich dagegen zweimal direkt hintereinander einfüge kommt der Stack-Overflow (wie oben beschrieben). So 'ne Scheiße, hab keinen Bock mehr. :(

[DocEW]

Hab's letztendlich hinbekommen... wenn auch ganz anders als geplant. Im Grunde kann man halt nicht wirklich so C-mäßig irgendwelche Variablen in Lisp ändern als wären es pointer. Was ich jetzt mache ist quasi die ganze Baumstruktur jedesmal neu aufbauen (ja ich weiß... aber selbst mein Prof. hat mir dazu gerate - was für eine Sprache!).

Also, der Vollständigkeit halber:
(defun insert_bst(element bst)

(let ( ( currentEl (first(first bst)) )
( numberEl (second(first bst)) )
( leftSubTree (second bst) )
( rightSubTree (third bst) )
)

( cond ( (<= element currentEl) ; if ( element <= current ) {
;
( cond ( (null leftSubTree) ; if ( current->leftSubtree == null ) {
(list (list currentEl (+ 1 numberEl)) ; "increase element
(buildLeaf element) ; counter and insert
rightSubTree ; new element here"
) ; }
) ;
( t ; else {
(list (list currentEl (+ 1 numberEl)) ; "increase element
(insert_bst element leftSubTree) ; counter and insert
rightSubTree ; element in left SubTree"
) ; }
) ;
) ;
) ; }
;
( t ; else {
( cond ( (null rightSubTree) ; if ( current->rightSubtree == null ) {
(list (list currentEl (+ 1 numberEl)) ; "increase element
leftSubTree ; counter and insert
(buildLeaf element) ; new element here"
) ; }
) ;
( t ; else {
(list (list currentEl (+ 1 numberEl)) ; "increase element
leftSubTree ; counter and insert
(insert_bst element rightSubTree) ; element in right SubTree"
) ; }
) ;
) ;
) ; }
)
)
)

[HellHorse]

Hab's letztendlich hinbekommen... wenn auch ganz anders als geplant. Im Grunde kann man halt nicht wirklich so C-mäßig irgendwelche Variablen in Lisp ändern als wären es pointer.
Ja, bloss hast du es imho für pairs/listen falsch gemacht. Auch das cond sieht jetzt korrekt aus.

Was ich jetzt mache ist quasi die ganze Baumstruktur jedesmal neu aufbauen (ja ich weiß... aber selbst mein Prof. hat mir dazu gerate
Pure funktional ohne Nebeneffekte, das passt schon.

- was für eine Sprache!).
Ich hoffe du meinst das im positiven Sinne. Falls nicht: freu dich schon mal auf Haskell ;) Da kannst du alle Nebeneffkte vergessen.

Also, der Vollständigkeit halber:
....
Geht imho auch einfacher:

(defun insert_bst(element bst)
(if (null bst)
(buildLeaf element)
(let ( ( currentEl (first(first bst)) )
( numberEl (second(first bst)) )
( leftSubTree (second bst) )
( rightSubTree (third bst) )
)
(if (<= element currentEl) ; if ( element <= current ) {
;
(list (list currentEl (+ 1 numberEl)) ; "increase element
(insert_bst element leftSubTree) ; counter and insert
rightSubTree ; element in left SubTree"
) ; }
; else {
(list (list currentEl (+ 1 numberEl)) ; "increase element
leftSubTree ; counter and insert
(insert_bst element rightSubTree) ; element in right SubTree"
) ; }
) ;
) ; }
)
)

Ungetestet, natürlich ;)

[Trap]

Nebenwirkung ist IMO die richtige Übersetzung von side effect.

Haskell hat auch Nebenwirkungen sonst wäre kein IO möglich, nur ist das irgendwie in dem Monaden-Konzept versteckt. Viel besser gelöst find ich das bei Clean mit uniqueness typing: http://www.cs.ru.nl/~clean/
Da gibt es Nebenwirkungen, aber nur für Dinge auf die genau 1 Referenz existiert.

Ich hab noch keinen Lisp-Code aus großen Programmen gelesen in dem Klammer eigene Zeilen bekommen...

[HellHorse]

Haskell hat auch Nebenwirkungen sonst wäre kein IO möglich, nur ist das irgendwie in dem Monaden-Konzept versteckt.
Ok, die Ausnahme zu der Regel.

Ich hab noch keinen Lisp-Code aus großen Programmen gelesen in dem Klammer eigene Zeilen bekommen...
Ich auch nicht, aber jedem das seine.

[DocEW]

Ich hoffe du meinst das im positiven Sinne. Falls nicht: freu dich schon mal auf Haskell ;) Da kannst du alle Nebeneffkte vergessen.
Nein, meinte ich nicht positiv. Ich mag weder Haskell noch Lisp noch Prolog besonders... ist irgendwie nicht meine Art zu denken. =)

Geht imho auch einfacher:
Oh ja, das sieht gut aus...der ganze Umstand mit der zusätzlichen Fallunterscheidung war noch aus der anderen Version, Mist. Naja zu spät, schon abgegeben. Trotzdem nochmal danke! =)


Ich hab noch keinen Lisp-Code aus großen Programmen gelesen in dem Klammer eigene Zeilen bekommen...
Wie würdet ihr das denn formatieren? Ich hab irgendwie versucht, die Schachtelungsebenen klar zu machen...

[Trap]

Übliche Formatierung ist so wie da:
http://lib1.store.vip.sc5.yahoo.com/lib/paulgraham/onlisp.lisp