函数式实现下基于特征函数的集合子集关系判断方法

方案说明 #

首先明确一个前提：如果是没有附加任何元信息的任意特征函数集合，不可能在不遍历全论域的情况下判断子集关系——特征函数本质是不透明的黑盒，你无法直接推导它的判断逻辑，只能通过输入测试验证。

但你给出的实现中所有集合都是有限元素枚举构造的，我们可以利用闭包的特性，给集合增加枚举元素的隐式记录能力，只需要遍历子集候选的所有元素逐一验证即可，完全不需要涉及论域的其他元素。

兼容现有接口的实现方案 #

我们只需要修改集合构造逻辑，让集合函数可以响应特殊的内部查询返回自身的所有元素，原有对外的使用接口完全不需要调整：

; 空集合响应查询返回空列表
(define EMPTY-SET 
  (lambda (x) 
    (if (equal? x '__get_elements)
        '()
        #f)))

(define (set-contains? maybe-elem set)
  (set maybe-elem))
 
(define (set-add to-add set)
  (lambda (x)
    (cond
      ; 响应查询返回当前集合的所有元素
      ((equal? x '__get_elements) (cons to-add (set '__get_elements)))
      (else (or (equal? x to-add) (set x))))))
 
(define (list->set l)
  (foldr set-add EMPTY-SET l))
 
(define (intersect set1 set2)
  (lambda (x)
    (cond
      ; 交集的元素就是set1中同时属于set2的元素
      ((equal? x '__get_elements) (filter (lambda (e) (set-contains? e set2)) (set1 '__get_elements)))
      (else (and (set-contains? x set1) (set-contains? x set2))))))

subset? 实现代码 #

(define (subset? set1 set2)
  ; 只需要遍历set1的所有元素，检查是否都属于set2即可
  (andmap (lambda (elem) (set-contains? elem set2))
          (set1 '__get_elements)))

测试示例 #

(define ex-set-1 (list->set (list 1 2 3 4)))
(define ex-set-2 (list->set (list 3 4 5 6)))
(define ex-set-3 (list->set (list 3 4)))

(display (subset? ex-set-3 ex-set-1)) ; 输出 #t
(display (subset? ex-set-3 ex-set-2)) ; 输出 #t
(display (subset? ex-set-1 ex-set-2)) ; 输出 #f

扩展场景说明 #

如果需要支持无限集合（比如(lambda (x) (> x 5))这种取值范围无限的集合）的子集判断，就需要额外引入符号推导或者类型系统能力，识别两个特征函数的逻辑包含关系，普通的闭包特征函数无法实现这类判断。

内容的提问来源于stack exchange，提问作者user4591818