将传递函数从 Python 转换为 Racket

Question

我想在Racket中实现这个功能。我如何在 Racket 中重写这个函数？

我的代码在 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? 将一对列表作为其唯一输入。该对列表表示二元关系。如果该二元关系具有传递性，则该函数应该 return #t，如下所示。

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

到目前为止，这是我在 Racket 中拥有的内容：

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

它仅在(exist-all-transitive-relations-of? x r set) 为真时有效。

这是我的输出：

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

如何修改我的代码？这样我就不必单独测试 (define (exist-all-transitive-relations-of? x r set) 是否为真

Answer 1

关于您在这里的球拍的一些评论：

当你这样做时：

(if (condition) #f (else))

你可以使用短路将其转换为

(and (condition) (else))

类似于

(if (condition) #t (else))

做

(or (condition) (else))

最后，在考虑替换 python 中的 for 循环时，考虑现有的列表抽象非常重要。在这种情况下，如果一个成员的属性中断，您将获取一个列表并将其压缩为一个数据，特别是一个布尔值。因此，您应该使用 andmap 这将大大减少您的代码：

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

注意：如果需要，(,a ,d) 可以替换为 (list a d)（无准引号）。 first 和 second 与 car 和 cadr.

将传递函数从 Python 转换为 Racket

Convert Transitive Function From Python to Racket

python

racket

relation