Scheme中COND与IF在Lambda/map场景下的差异及幂集函数问题

先看你提供的两段代码：

(define (subset set)
    (display set)
    (cond
      ((null? set) '() )
      (else
       (append (subset (cdr set))
                   (map (lambda (subset) (cons (car set) subset))
                         (subset (cdr set)))))
     )
  )
  
 (define (power-set set)
    (display set)
    (if (null? set) '(())
             (append (power-set (cdr set))
                   (map (lambda (power-set) (cons (car set) power-set))
                         (power-set (cdr set))))))
  
(subset '(a b c))

(power-set '(a b c))

核心差异在于基础情况的返回值：

• subset函数处理空集时返回'()（空列表）
• power-set函数处理空集时返回'(())（包含空列表的列表，也就是空集的幂集）

为什么这个差异会导致完全不同的结果？ #

幂集的定义是：一个集合的幂集是它所有子集的集合，包括空集本身。所以空集的幂集不是空列表，而是一个只包含空集的集合——也就是'(())。

我们一步步拆解递归过程：

1. 对于subset函数：

   • 当处理空集'()时，返回'()
   • 处理'(c)时：
     • (subset (cdr '(c)))调用subset '()，返回'()
     • map部分对空列表执行cons 'c，得到的还是空列表
     • append两个空列表，结果还是'()
   • 往上递归到'(b c)、'(a b c)时，每一步的append操作都是合并两个空列表，最终返回'()

2. 对于power-set函数：

   • 当处理空集'()时，返回'(())
   • 处理'(c)时：
     • (power-set (cdr '(c)))调用power-set '()，返回'(())
     • map部分对'(())中的每个元素执行cons 'c，得到'((c))
     • append这两个结果，得到'(() (c))——这正是'(c)的正确幂集
   • 处理'(b c)时：
     • power-set '(c)返回'(() (c))
     • map部分得到'((b) (b c))
     • append后得到'(() (c) (b) (b c))
   • 最终处理'(a b c)时，会合并低一层的幂集和新增的带a的子集，得到完整的幂集：'(() (c) (b) (b c) (a) (a c) (a b) (a b c))

另外注意：两个函数里的display语句会在递归过程中打印出各个子集合，但这只是调试输出，不影响最终返回值的逻辑。

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