Convert Transitive Function From Python to Racket

Question

I would like to implement this function in Racket. How could I rewrite this function in Racket?

My CODE IN PYTHON

# function to check transitive relation
def is_transitive(relation):
    # for all (a, b) and (b, c) in Relation ; (a, c) must belong to Relation
    for a,b in relation:
        for c,d in relation:
            if b == c and ((a,d) not in relation):
                return False
    return True

transitive? takes a list of pairs as its only input. That list of pairs represents a binary relation. The function should return #t if that binary relation is transitive, as illustrated below.

> (transitive? '((1 2) (2 3) (1 3)))
#t
> (transitive? '((1 3) (1 2) (2 3)))
#t
> (transitive? '((1 2) (2 3)))
#f
> (transitive? '((1 1) (1 2) (2 1) (2 2) (3 3)))
#t
> (transitive? '((1 2) (3 3) (2 2) (2 1) (1 1)))
#t
> (transitive? '((2 3) (3 3) (1 2) (1 1)))
#f

Here is what I have in Racket so far:

(define (get-all-relations-of x set)
  (if (null? set)
      '()
      (if (equal? x (car (car set)))
          (cons (cdr (car set))
                (get-all-relations-of x (cdr set)))
          (get-all-relations-of x (cdr set)))))
    
(define (exist-relation? r set)
  (if (null? set)
      #f
      (if (equal? r (car set))
          #t
          (exist-relation? r (cdr set)))))
    
(define (exist-all-transitive-relations-of? x r set)
  (if (null? r)
      #t
      (if (not (exist-relation? (cons x (car r)) set))
          #f
          (exist-all-transitive-relations-of? x (cdr r) set))))
    
(define (transitive? set)
  (if (null? set)
      #t
      (if (and (not (null? (get-all-relations-of (cdr (car set)) set)))
               (not (exist-all-transitive-relations-of?
                     (car (car set))
                     (get-all-relations-of (cdr (car set)) set)
                     set)))
          #f
          (transitive? (cdr set)))))

It only works when(exist-all-transitive-relations-of? x r set) is true.

Here is my output :

>(exist-all-transitive-relations-of? 1 '(2 5 6) '((1 2) (1 5) (6 8)))))
> #t
>(define (transitive? '((1 2) (2 6)))
> #f
>(define (transitive? '((1 2) (2 6)(2 7)(1 7)))
> #f
>(define (transitive? '((1 2) (2 6)(2 7)(1 7)(1 6)))
> #t

How can I modify my code? so that I don't have to test if (define (exist-all-transitive-relations-of? x r set) is true separately

And what have you tried so far? Any Racket code you care to share? — mkam
Does the Racket code work? If not, what is going wrong? Have you checked get-all-relations-of, exist-relation?, and exist-all-transitive-relations-of? with test cases to find out if they are behaving as expected? — ad absurdum
the code works only if I test for exist-all-transitive-relations-of? first — user14581149
What is the expected output for your given examples? Because the python code gives the exact same output for all of your examples — Ryan Schaefer

Ryan Schaefer Ryan Schaefer · Accepted Answer · 2020-11-05T18:52:35

Just a few comments on the racket you have here:

When you do:

(if (condition) #f (else))

you can use short circuiting to convert it to

(and (condition) (else))

Similar for

(if (condition) #t (else))

do

(or (condition) (else))

Finally, it is very important to consider the existing list abstractions when thinking about replacing for loops in python. In this case you are taking a list and condensing it down into one piece of data specifically a boolean if the property breaks for one member. Therefore, you should use andmap which will drastically reduce your code:

(define (transitive? set)
  (andmap (lambda (x) (andmap (lambda (y)
       (local [(define a (first x))
               (define b (second x))
               (define c (first y))
               (define d (second y))]
       (not (and (= b c) (not (member `(,a ,d) set)))))) set)) set))

Notes: (,a ,d) can be replaced with (list a d) (no quasiquote) if you want. And first and second with car and cadr.

Convert Transitive Function From Python to Racket

1 Answers