[racket] side-effect-free DFS of k-ary tree?

From: Ben Dean (bddbbd.b at gmail.com)
Date: Mon Dec 30 01:23:23 EST 2013

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>

Posted on the users mailing list.