CODEWITHSUNDEEP
schemelispsicp
ConCat
ConCat

Reputation: 25

Keeping sublists in list form

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.

Upvotes: 1

Views: 166

Answers (2)

Will Ness
Will Ness

Reputation: 71065

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?).

Upvotes: 1

Sylwester
Sylwester

Reputation: 48745

Your code looks you are learning Scheme by applying knowledge from Algol programming experience (like C or Java). In Scheme you should try to do your programming without mutation unless you have a really good reason to do so. Keeping most of the procedures pure means it's easier to test.

Naming convention is important and a procedure that ends in ? is a predicate and thus it should return one of two values, #t or #f just like isString should return true/false in Algol languages. 

;; graph constructor/accessors not not use car, cadr, etc
;; later you can change it to boxes
(define (make-graph from to weight)
  (list from to weight))
(define graph-from car)
(define graph-to cadr)
(define graph-wight cddr)

;; gets the graphs that has node as starting point
(define (graphs-from node graphs)
  ; match? returns #t if graph starting point is the same as node
  ; since it's symbols we use eq?
  (define (match? graph)
    (eq? node (graph-from graph)))

  ; filters data by starting point
  ; this is the tail expression and thus the result of this procedure
  (filter match? graphs))

(define data (list (make-graph 'x 'y 20)
                   (make-graph 'y 'x 30)
                   (make-graph 'w 'e 20)
                   (make-graph 'x 'e 13)))

(graphs-from 'x data)
; ==> ((x y 20) (x e 13))

(graphs-from 'a data)
; ==> ()

Upvotes: 1

Related Questions