I am working on a homework assignment to traverse a DAG, finding the shortest route. With the help of some SO answers, I have quite a few pieces in place. That being said, I am having trouble getting a function to return a list of sublists like I need to further deal with the data. The data file has a list of sublists in the form (node1 node2 weight)
(define (children? node)
(define list '(1))
(map (lambda (x)
(cond
((equal? (car x) node)
(if (equal? list '(1))
(set-car! list x)
(append! list x)))))
data)
(if (equal? list '(1))
#f
list))
(define (append! lst . lsts)
(if (not (null? lsts))
(if (null? (cdr lst))
(begin
(set-cdr! lst (car lsts))
(apply append! (car lsts) (cdr lsts)))
(apply append! (cdr lst) lsts))))
When I run (children? 'b3), I get a result that looks like:
((b3 b5 57) b3 b4 81 b3 b10 55 b3 b14 61 b3 b13 66)
When it should actually look like
((b3 b5 57) (b3 b4 81) (b3 b10 55) (b3 b14 61) (b3 b13 66))
Can anyone shine a little light on my problem here?
Thanks in advance for your help.
Fixing the indentation, your code becomes
(define (children? node)
(define list '(1))
Using the head sentinel trick. Good (well...). But since its purpose is to be surgically altered, it should be freshly made, not quoted datum:
(define list (list 1))
wait, what? Two lists? This is not Common Lisp, is it? Scheme is a Lisp-1, not Lisp-2; The names of functions and values live in the same namespace; so; don't.
(define lst (list 1))
(map (lambda (x)
(cond
((equal? (car x) node)
(if (equal? list '(1))
(set-car! list x)
(append! list x)))))
Two conditions in a row is just an and, but more importantly, the head sentinel trick means you'll return the true result as (cdr lst), so there's no need to alter its head's contents. The code then simplifies, which is the whole purpose of using the head sentinel in the first place:
(map (lambda (x)
(if (equal? (car x) node)
(append! lst x))) ; changed the name
no alternate clause? In general, frowned upon, but here you do the map for its side-effect, so, as long as you do not use the map's result, you're fine. Easier though is to just always handle the alternate clause as a matter of habit and good style, like
(map (lambda (x)
(if (equal? (car x) node)
(append! lst x) ; append two lists together... (see below)
#f))
data)
data? What is that? It should be added as another formal parameter of children?.
(if (equal? lst '(1))
equal?? Why? To see whether we've altered it, it is enough to just
(if (null (cdr lst))
the least action principle...
#f
(cdr lst))) ; cdr carries the true payload
(So basically,
(define (children? node data)
(let ((res (filter (lambda (x) (equal? (car x) node))
data)))
(if (not (null? res))
res
#f)))
). Good. Is it? Well, it depends on the following working correctly.
(define (append! lst . lsts)
(if (not (null? lsts))
(if (null? (cdr lst))
(begin
(set-cdr! lst (car lsts))
(apply append! (car lsts) (cdr lsts)))
It appends lists, so (append! (list 1) (list 2)) will return the same result as (list 1 2) and (append! (list 1) (list 2 3)) the same as (list 1 2 3). To add an item (like 2) at a list's end we had to put it inside another list first. So if our item being added is itself a list, like '(2 3), we want to get '(1 (2 3)) back. And for that, an item must be enclosed in a list before being appended. So your function must be amended to do that.
(apply append! (cdr lst) lsts))))
And here you scan through your (growing) result list to find its last cell, again and again for each item being added. You can remedy that by maintaining the last cell pointer yourself, and using it directly. What's that "pointer"? it's lst, which you cdr each time you append! something to it; so you can do (set-cdr! lst (list item)) directly yoursef. You can't of course use lst variable for that (why?).