如何在 Lisp R5RS 中编写幂集

Question

我是函数式编程的新手，我不知道如何用 Lisp 编写代码。例如，对于给定的幂集，例如 (1 2 3)，我如何以某种方式对其进行编码：（不使用 Lambda 函数） ( () (1) (2) (3) (1 2 3) )

到目前为止，我有：

(define  (powerSet lis)
  (if (null? lis) '(()))
 )

(define (APPENDS lis1 lis2)
   (cond
   ((null? lis1) lis2)
        (else (cons (car lis1)
            (APPENDS (cdr lis1) lis2)))
  )
)

这只是 returns 空集，或者什么都没有。

编辑：

非常感谢克里斯！这很有道理。第二种变体（没有 append-map 函数）效果很好。但是，如果您输入 (powerset'(1 2 3 4))，它会为您提供：

(() (1) (2) (1 2) (3) (1 3) (2 3) (1 2 3) (4) (1 4) (2 4) (1 2 4) (3 4) (1 3 4) (2 3 4) (1 2 3 4))

我有没有办法让它看起来像：

(() (1) (2) (3) (4) (1 2) (1 3) (1 4) (2 3) (2 4) (3 4) (1 2 3) (1 2 4) (1 3 4) (2 3 4) (1 2 3 4))

非常感谢！

Answer 1

所有用户定义函数都是 lambda（或 case-lambda）表达式，包括您正在定义的 powerset 函数。没有办法避免它。但是，您可以使用内部定义隐藏 lambda 标识符（它仍然是幕后的 lambda！^†）。

考虑到这一点，这里有一个实现（需要 Racket 或 SRFI 1）：

(define (powerset lst)
  (define (make-pair x)
    (list x (cons (car lst) x)))
  (if (null? lst)
      '(())
      (append-map make-pair (powerset (cdr lst)))))

如果你想避免 append-map 或一般的高阶函数，你可以跳过几个步骤来做同样的事情：

(define (powerset lst)
  (define (inner next)
    (if (null? next)
        '()
        (cons (car next)
              (cons (cons (car lst) (car next))
                    (inner (cdr next))))))
  (if (null? lst)
      '(())
      (inner (powerset (cdr lst)))))

^† 像

这样的表达式

(define (foo bar)
  baz)

实际上展开为如下等价表达式：

(define foo
  (lambda (bar)
    baz))

如何在 Lisp R5RS 中编写幂集

How to code Power Set in Lisp R5RS

set