closuresracketsymmetric

Racket: How can I fix my code so that it will return all the flipped pairs that is missing?


This function should return the symmetric closure of L. Examples:

(Symmetric-Closure'((a a) (a b) (b a) (b c) (c b))) ---> '((a a) (a b) (b a) (b c) (c b))
(Symmetric-Closure'((a a) (a b) (a c))) ---> '((a a) (a b) (a c) (b a)(c a))
(Symmetric-Closure'((a a) (b b))) ---> '((a a) (b b))
(Symmetric-Closure'())---> '() 

Here is what I have in Racket

(define (Symmetric-Closure L)
  ;Iterate over each pair in L
  (andmap (lambda (x)
             ;If the flipped pair does not exist in L, it will
             ;return L and the flipped pair that is missing. Otherwise, return L.
             (if(not(member (list (cadr x)(car x)) L))
                (cons (list (cadr x)(car x)) L)
                (append L)))
           L))

How can I fix my code so that it will return all the flipped pairs that is missing For example, my code only return L and the last missing flipped pair (c a) instead of (b a) and (c a)

;this is wrong, it should return '((c a)(b a)(a a)(a b)(a c))
(Symmetric-Closure '((a a)(a b)(a c))-----> '((c a)(a a)(a b)(a c)) 
;this is correct
(Symmetric-Closure '((a a)(a b)(b a)(b c)(c b)))-----> '((a a)(a b)(b a)(b c)(c b)) 

Solution

  • andmap means "map the list using this function and then and together the results." In Racket, whenever you and together any values, the result is going to be either the last value provided to it, or false. For example, (and value1 value2) results in value2 if neither value1 nor value2 is false (and if one of them is false, the result is false as well). Since the value produced by your lambda is never false, the result of your andmap is going to be the value of the lambda expression the final time it is called, which in this case, could be the list (cons (list (cadr x)(car x)) L) for the last value of x that it sees in the original list L. This means that all preceding values that were consed don't factor into the result at all.

    You could modify this to use a simple map instead. But this produces a list of lists of pairs, not a list of pairs which is what you want. So at the end you need to flatten this to arrive at the result.

    (define (symmetric-closure L)
      ;Iterate over each pair in L
      (apply append
             (map (lambda (x)
                    ;If the flipped pair does not exist in L, it will
                    ;return L and the flipped pair that is missing. Otherwise, return L.
                    (if (not (member (list (cadr x) (car x)) L))
                        (list (list (cadr x) (car x)) x)
                        (list x)))
                  L)))
    

    One thing to be aware of, though, is that this algorithm calls member for every element in the original list. Checking for membership in a list is O(N) and you are doing this N times, meaning that the complexity of this algorithm is O(N²). You should be able to do this more efficiently, for instance by using a hash set.