CODEWITHSUNDEEP
scheme
asdf
asdf

Reputation: 667

Scheme - checking structural equivalences of lists (how to use AND)

I am trying to write a program that will check the structural equivalence of some list input, whether it includes just atoms or nested sub lists.

I am having trouble with using AND, I don't even know if its possible and I cant seem to understand documentation I am looking at.

My code:

 (define (structEqual a b)
   (cond
     (((null? car a) AND (null? car b)) (structEqual (cdr a) (cdr b)))
     (((null? car a) OR (null? car b)) #f)
     (((pair? car a) AND (pair? car b)) 
      (if (= (length car a) (length car b))
          (structEqual (cdr a) (cdr b))
          #f))
     (((pair? car a) OR (pair? car b)) #f)
     (else (structEqual (cdr a) (cdr b)))))

The idea is (i think): (when I say both, i mean the current cdr of a or b)

  1. Check if both a and b are null, then they are structurally equal

  2. Check if only either a or b is null, then they are not structually equal

  3. Check if both of them are pairs

  4. If they are both pairs, then see if the length of the pair is equal, if not they are not structurally equal.

  5. If they are not both pairs, then if one of them is a pair and the other isnt then they are not structurally equivalent.

  6. If neither of them are pairs, then they both must be atoms, so they are structurally equivalent.

So as you can see I am trying to recursively do this by checking the equivalence of the car of a or b, and then either returning #f if they fail or moving on to the cdr of each if they are equivalent at each step.

Any help?

Upvotes: 0

Views: 108

Answers (1)

Sylwester
Sylwester

Reputation: 48745

There is no infix operators in Scheme (or any LISP) only prefix. Every time the operator comes first. (or x (and y z q) (and y w e)) where each letter can be a complex expression. Everything that is not #f is a true value. Thus (if 4 'a 'b) evaluates to a because 4 is a true value. car needs its parentheses.

When evaluating another predicate in cond you should make use of the fact that everything up to that has been false. eg.

(define (structure-equal? a b)
  (cond
    ((null? a) (null? b))                                ; if a is null the result is if b is null
    ((not (pair? a)) (not (pair? b)))                    ; if a is not pair the result is if b is not also
    ((pair? b) (and (structure-equal? (car a) (car b))   ; if b is pair (both a and b is pair then) both 
                    (structure-equal? (cdr a) (cdr b)))) ; car and cdr needs to be structurally equal
    (else #f)))                                          ; one pair the other not makes it #f

(structure-equal '(a (b (c d e) f) g . h) '(h (g (f e d) c) b . a)) ; ==> #t

Upvotes: 4

Related Questions