[racket] side-effect-free DFS of k-ary tree?
I'm trying to do a simple depth-first search of a tree in Racket,
ultimately returning a list of nodes up to the node I'm searching for. I
want to do this side-effect-free, if possible, and I'm running into a wall
with the approach I started on...
This is my current implementation:
-------------------Begin Code---------------------------
#lang racket
(define example-tree '("E"
("B"
("S"))
("U"
("V")
("T"
("H"
("G"))))))
(define (parents node tree branch backtrack)
(letrec ([children (if (pair? tree)
(cdr tree)
'())]
[extended-branch (cons (car tree) branch)]) ;optimistically add
it to the working branch
(cond
[(equal? node (car tree)) branch] ; found the node, return the branch
[(empty? children) (backtrack)]
[else (parents ;the recursive case
node ;still looking for the same node
(car children) ;search the first child node
extended-branch
(if (> (length children) 1)
(λ () (parents node (cdr children) extended-branch
backtrack)) ;store the search
backtrack))])))
(parents "H" example-tree '() (λ () "Node Not Found"))
---------------------End Code----------------------------------
The output I should see is '("T" "U" "E")
The output I get is "Node Not Found"
I've been debugging in Dr. Racket, and the confusion sets in when calling
backtrack after hitting node "S". It appears to do what I expect--calls
(parents "H" '("U" ("V") ("T" ("H" ("G"))))) '("E") (λ () "Node Not
Found"))
I think... I'm not so sure about the value of the final argument,
backtrack, here. Is there a way to examine the procedure in more detail
from the debugger?
Anyhow, this is all more or less what I intended with the code, but
stepping through this call to parents does not continue as I had hoped.
Children is bound to '() though I would have expected '(("V") ("T" ("H"
("G"))). extended-branch is bound to '(("U" ("V") ("T" ("H" ("G"))))
("E")), where I would have expected ("U" "E").
So, the number one question is, does this general approach even make sense?
If so, is the problem here in the logic (still kinda rough, I know) or am
I cdring where I ought to be cadring in some spot? Or if this approach is a
non-starter, where should I look for a way to do this? Thanks for the help.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20131229/ab3d174e/attachment.html>