[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