CODEWITHSUNDEEP
duplicatesschemerackettransitive-closure
user14581149
user14581149

Reputation: 55

How can I fix my code to avoid returning duplicate pairs while using map in racket?

This function should return the transitive closure of L. For Examples:

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

Here is what I have in Racket:

(define (Transitive-Closure L)
  (apply append
  ; Iterate over each pair (a b) in L,
  (map (lambda (x)
            ;Iterate over each pair (c d) in L,
            (map (lambda (y)
                      (let ([a (car x)]
                            [b (cadr x)]               
                            [c (car y)]
                            [d (cadr y)])
                        ;if b equal to c, and (a d) does not exist in L, it will add (a d) to L . Otherwise, return L.
                        (if  (and (eq? b c) (not (member (list a d) L)))
                             (list a d)
                             (append x))))L)) L)))

My code only works when it's not transitive. How can I modify my code to avoid returning duplicate pairs when it's transitive?

For example, my Output:

;This is wrong. It should return '((a b)(b c)(a c)) 
(Transitive-Closure '((a b)(b c)(a c))) ---> '((a b) (a b) (a b) (b c) (b c) (b c) (a c) (a c) (a c))
; This is right.
(Transitive-Closure '((a b)(b a)))---> '((a b) (a a) (b b) (b a))

Upvotes: 0

Views: 268

Answers (1)

Ryan Schaefer
Ryan Schaefer

Reputation: 3120

This isn't a map problem this is a foldr problem because you aren't modifying the list in place, you are condensing the list down into one item. That item happens to be a list but importantly that list can be smaller than what map can return. Also you can check if you should add or not in another if statement based on if the pair already exists in our accumulator.

This works if order doesn't matter (which I am assuming, you just want the set, let me know if this is not the case)

(define (Transitive-Closure L)
  ; Iterate over each pair (a b) in L,
  (foldr (lambda (x transitive-pairs)
            ;Iterate over each pair (c d) in L,
            (foldr (lambda (y sofar)
                      (let ([a (car x)]
                            [b (cadr x)]               
                            [c (car y)]
                            [d (cadr y)])
                        ;if b equal to c, and (a d) does not exist in L, it will add (a d) to L . Otherwise, return L.
                        (cond [(and (eq? b c) (not (member (list a d) L))) (cons (list a d) sofar)]
                              [(not (member x sofar)) (cons x sofar)]
                              [else sofar])))
                               transitive-pairs L)) '() L))

(check-expect (Transitive-Closure '((a b) (b c) (a c))) '((a b) (b c) (a c)))
(check-expect (Transitive-Closure '((a a) (b b) (c c))) '((a a) (b b) (c c)))
(check-expect (Transitive-Closure '((a b) (b a))) '((a b) (a a) (b b) (b a)))
(check-expect (Transitive-Closure '((a b) (b a) (a a))) '((a b) (b b) (b a) (a a)))
(check-expect (Transitive-Closure '((a b) (b a) (a a) (b b))) '((a b) (b a) (a a) (b b)))

Upvotes: 2

Related Questions