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