测试函数关系和一对一关系的方案过程

Question

集合A和B之间的关系R称为泛函，如果对于集合A中的任何元素a，在集合B中存在唯一的元素b，使得对(a，b)在集合R中。

(functional '(1 2 3) '(4 5 6) '((1 4) (2 4) (3 5))
; ==> #t
(functional '(1 2 3) '(4 5 6) '((1 4) (1 6) (2 5) (3 5))
; ==> #f

一对一

(one-to-one '(1 2 3) '(4 5 6 7) '((1 4) (2 6) (3 7))
; ==> #t
(one-to-one '(1 2 3) '(4 5 6 7) '((1 4) (2 4) (3 7))
; ==> #f

下面是我的一对一的代码

(define one-to-one
  (lambda (a b r)
    (cond
      ((null? r)
       #t)
      ((one-to-one-helper (first r) (rest r))
       #f)
      (else
       (one-to-one a b (rest r))))))

(define one-to-one-helper
  (lambda (pair set)
    (cond
      ((null? set)
       #f)
      ((eq? (rest pair) (rest (first set)))
       #t)
      (else
       (one-to-one-helper pair (rest set))))))

我的第二个测试程序应该返回false，但它返回true

Answer 1

第二个测试用例产生false的原因是因为您的one-to-one-helper函数在测试相等性时使用了eq?。举例说明：

> (eq? '(4) '(4))
#f
> (eqv? '(4) '(4))
#f
> (equal? '(4) '(4))
#t

然而，

> (eq? 4 4)
#t
> (eqv? 4 4)
#t
> (equal? 4 4)
#t

因此，要解决您的问题，您可以更改为equal?

((equal? (rest pair) (rest (first set)))

或者在原子元素上进行比较：

((eq? (cadr pair) (cadar set))

下面是一个注入式(一对一)谓词函数的示例实现，使用equal?进行比较：

(define (injective? mapping)
  (define (one-to-one? pair mapping)
    (or (null? mapping)
        (and (not (equal? (cadr pair) (cadar mapping)))
             (one-to-one? (car mapping) (cdr mapping)))))
  (or (null? mapping)
      (and (one-to-one? (car mapping) (cdr mapping))
           (injective? (cdr mapping)))))

例如,

> (injective? '((1 4) (2 6) (3 7)))
#t
> (injective? '((1 4) (2 4) (3 7)))
#f