scheme - 这个 Scheme 程序的错误在哪里？

Question

我收到“错误：无效的 lambda：(lambda (insert-all))。”

(define permutations
 (lambda (L)
  (let
   ((insert-all
    (lambda (e Ls)
     (let
     ((insert-one
      (lambda (L)
       (letrec
        ((helper
         (lambda(L R)
         (if (null? R)
          (list (append L(list e)R))
          (helper (append L (list (car R) ) ) (cdr R) )
          ))))
          (helper '() L)))))
          (apply append(map insert-one Ls)))))))

  (cond ((null? L) '() )
  ((null?(cdr L)) (list L))
  (else (insert-all (car L) (permutations ((cdr L))))))))

它应该返回给定列表的所有排列。

Answer 1

您在无效方案中提供的表格。具体来说，您的最高级别let表单没有主体。您可能认为该cond子句是主体，但由于您的括号，它不是let. 老实说，这是您格式的错误。这是一个“正确”格式的方案表单：

(define (permutations L)
  (let ((insert-all
         (lambda (e Ls)
           (let ((insert-one
                  (lambda (L)
                    (let helper ((L '()) (R L))
                      (if (null? R)
                          (list (append L (list e) R))
                          (helper (append L (list (car R)))
                                  (cdr R)))))))
             (apply append (map insert-one Ls))))))

    (cond ((null? L)       '())
          ((null? (cdr L)) (list L))
          (else (insert-all (car L)
                            (permutations (cdr L)))))))

至少它可以编译并运行，尽管它不会产生正确的答案（尽管我不知道它的正确输入是什么）：

> (permutations '(a b c))
((c b a))
> (permutations '((a b) (1 2)))
(((1 2) (a b)))

这是一个有效的实现：

(define (permutations L)
  (define (insert-all e Ls)
    (apply append 
           (map (lambda (e) 
                  (map (lambda (x) (cons e x)) Ls))
                e)))
  (cond ((null? L)       '())
        ((null? (cdr L)) (map list (car L)))
        (else (insert-all (car L)
                          (permutations (cdr L))))))


> (permutations '((a b) (1 2) (x y)))
((a 1 x) (a 1 y) (a 2 x) (a 2 y) (b 1 x) (b 1 y) (b 2 x) (b 2 y))

您的代码的基本结构很好；只是你的执行insert-one和helper缺乏。