Anomalous Behavior Comparing Lists in DrRacket

Question

I am attempting to write a program that checks whether or not a list of lists has a certain property (unimportant to the question). Along the way I found it necessary to produce the list of "non-diagonal pairs" of a single given list, so I wrote a macro that takes a list and defines both the list of pairs (a list-version of the Cartesian product of sets) and what I'll call the "diagonal" of that list (pairs of the form '(x x)). The code I've written to accomplish this is below:

;;;These first two definitions are 'extended' car and cdr
;;;I only did this because the (prod a b) code below threw errors otherwise
(define (xcar a) (cond ((null? a) '()) ((car a))))
(define (xcdr a) (cond ((null? a) '()) ((cdr a))))

;;;This defines a pre-product, i.e. all pairs with the first element of the first list
(define (pre-prod a b)
    (cond ((or (null? a) (null? b)) '())
    ((append (list (list (xcar a) (xcar b))) (pre-prod a (xcdr b))))))

;;;This defines the full product of the list
(define (prod a b)
    (cond ((null? a) '())
    ((append (pre-prod a b) (prod (xcdr a) b)))))

;;;This defines the diagonal of the list
(define (diagonal a)
    (cond ((null? a) '())
    ((append
      (list (list (car a) (car a)))
      (diagonal (cdr a))))))

Great, that code all seems to work just like I want it to. I next needed to take a list-version of the set-minus. I found the following code to do exactly this in an answer here:

;;;Returns #t if x is an element of lst and #f otherwise
(define (element? x lst)
    (cond ((null? lst) #f)
    ((eq? x (car lst)) #t)
    (#t (element? x (cdr lst)))))

;;;Takes list a and removes all elements of list b from it
(define (list-minus a b)
    (cond ((null? a) '())
    ((element? (car a) b)
     (list-minus (cdr a) b))
    (#t (cons (car a) (list-minus (cdr a) b)))))

Cool, that seems to work just fine for what it needs to do. Now all I have to do is get DrRacket to return the list of proper pairs (removing the diagonal). I figure that the following code ought to do it:

(define (proper-pairs a) (list-minus (prod a a) (diagonal a)))

Now I test this new function on something easy, where it should return '():

>  (proper-pairs '(1))
=> '((1 1))

WHAT? I've tried a lot of examples, reworked the code several times, tried it on various lists of lists. I always come up with the following problem: list-minus will not remove a list from a list of lists.

Question 1: Why does list-minus exhibit this anomalous behavior on lists of lists while working exactly as expected on things like the following example:

>  (list-minus '(1 2 3 4 5) '(x 2 4 m))
=> '(1 3 5)

Question 2: How do I repair the list-minus code, or is it necessary to start from scratch?

Question 3: In the very first lines of code above I had to "extend" the car and cdr to ensure that the prod function would not throw an error. Is what I did a standard trick? I'm not sure I understand why it makes a difference (I just tried it in because I had a hunch it might work).

Disclaimer: I am not a programmer. I'm trying to learn functional programming as a means of testing various (mathematical) conjectures and compiling some examples. I have absolutely no experience writing code other than some very silly little bits that I've done in DrRacket and on an old TI-83 calculator. This being said, it will probably be necessary to "dumb-down" your answers for me.

Sorry for the long-windedness, and thank you for your time!

Answer 1

The problem is due to the fact that equality in Racket, like in other languages, is represented with different operators, that must be chosen according to:

1. the type of data that must be compared,

2. the semantics of the comparison.

The general hint is that you should use the operator which is logically more simple for the task and that can be used for a certain comparison.

For instance, you should use = to compare numbers; eq? to compare objects for identity i.e. two values are equal if the are the same object in memory; eqv? if you want to check that two values are the same object in memory or are equal numbers or equal characters; equal? if you want to check if two values are eqv? or if they are equal strings, or if they, being structured data like lists, are structurally equivalent (see the manual), i.e. recursively equivalent.

For instance:

(equal? '(a (b)) '(a (b)))  ; => true, two different objects with the same structure
(eqv? '(a (b)) '(a (b)))    ; => false, two different objects
(eq? '(a (b)) '(a (b)))     ; => false, as for eqv?
(let ((x '(a (b))))
  (eq? x x))                ; true, they are the same object