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

Teaser: You're missing an 'a' in a function name. (This gives the desired result and is a guess at what is in your mind.) 

Lesson: What you should really do, however---I mean instead of searching for the place where to insert the 'a'---is to design the code systematically. See How to Design Programs. (Yale people should know about this book. Ask Paul or Zhong.) 

Here is what the Teaser means: 

 1. data definition: What kind of data is parents really processing? I had to guess. Good programmers write that down. 
 2. signature/purpose: What is the purpose of parents? Well, you kind of said it. 
 3. example: I am glad you have an example. 
 4. template: Why does the organization of parents not match the description of the data that I imagine you are using? (That's the key hint.) 
 5. coding: Please do follow up on Daniel's suggestions concerning 'letrec' (why?), car/cdr (why live in the 1950s when it's 2014, almost?) 
 6. testing: do turn your example into a test using rackunit
    (require rackunit)  
    (check-equal? (parents example-tree ...) '("T" "U" "E"))

Q: Why use CPS immediately when a direct traversal would do the same? (That's what Daniel is asking.) 

If this doesn't help, holler. 




On Dec 30, 2013, at 1:23 AM, Ben Dean <bddbbd.b at gmail.com> wrote:

> 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.
> 
> 
> 
> ____________________
>  Racket Users list:
>  http://lists.racket-lang.org/users